You provide a generally correct impression of history (i.e., there were lots of runs on banks by depositors in the US until federal deposit insurance was established— a good history is provided by Gorton (2012)), and then ask three questions: why isn't deposit insurance provided through the private sector, is it because the free market equilibrium premiums would be too high, and if so, does this mean that the FDIC premiums are set too low?
To answer, we should first back up to the reason for deposit insurance generally, which is twofold:
- Monitoring costs
- Bank runs are a stable equilibrium
Then, we can discuss the reasons for government provision of deposit insurance specifically, which are:
- Externalities
- Monitoring costs (still)
- Moral hazard
- Systemic crises
The monitoring costs issue is a real one, and has been discussed in the literature by Diamond (1984), among others. It's derived from a prinicpal-agent issue: foremost, depositors want bank management to make safe investments that ensure that their deposits can be returned with certainty, while bank management is encouraged by its equity holders to take on as much risk as possible (for a general discussion of this principal-agent problem in the theory of the firm, see Hart (2001)). In short, management isn't looking out for depositors, and it's really expensive to ask all depositors to be aware at all times about the state of a bank's investments. This is additionally difficult as a practical matter, as bank balance sheets are not paragons of transparency.
Further, as Diamond and Dybvig (1983) showed, even if one ignores monitoring costs, bank runs are one stable equilibrium of a system without deposit insurance. The logic for this is described in your question: if an institution that holds illiquid assets is forced to liquidate them prior to maturity and within a short time period, it may face solvency issues as a result of that forced liquidation. This is known as the "solvency-liquidity nexus" and is discussed in a context including wholesale funding, as opposed to only deposit funding, in Pierret (2015). As a result, if depositors believe that a bank may face a run, it's rational for depositors to run on that bank even if it is fundamentally solvent. In fact, if one considers that a depositor's only recourse (in the event that monitoring reveals that management is taking on too much risk) is to withdraw his or her deposits, it should be clear that zero-cost monitoring of banks does not eliminate the possibility of runs.
So, why government-provided deposit insurance?
Perhaps the simplest reason, but the one that is least discussed in the literature, is that bank failures tend to occur together, as widespread episodes with significant externalities. For this reason alone, it's easy to understand why society (and on behalf of society, government) would have an interest in ensuring that they don't occur. But that doesn't really answer your question, which is, why doesn't the private sector handle the problem of bank runs through private insurance (and, contra another answer to this question, the private sector has never handled this issue well) so that the problem never becomes one that the government must address?
Well, a second reason would be that depositors would still face monitoring costs, as the value of the liquidity guarantee provided by a private insurer would only be as good as that entity's capacity to make good on its guarantees, which would require monitoring in turn. So that problem would still exist.
A third reason, as Diamond and Dybvig (1983) discussed in their conclusion, is that an insurer must be able to regulate the bank it's guaranteeing, because otherwise, the bank managers again have an incentive to make riskier choices:
The riskless technology used in the model isolates the rationale for
deposit insurance, but in addition it abstracts from the choice of bank
loan portfolio risk. If the risk of bank portfolios could be selected by a
bank manager, unobserved by outsiders (to some extent), then a
moral hazard problem would exist. In this case there is a trade-off
between optimal risk sharing and proper incentives for portfolio
choice, and introducing deposit insurance can influence the portfolio
choice. [...]
Introducing risky assets and moral hazard would be an interesting
extension of our model. It appears likely that some form of government
deposit insurance could again be desirable but that it would be
accompanied by some sort of bank regulation. Such bank regulation
would serve a function similar to restrictive covenants in bond indentures.
Interesting but hard to model are questions of regulator "discretion"
which then arise.
Given this need for a regulator where deposit insurance exists, it makes quite a bit of sense to build a legal framework around a single regulator-insurer, which we've done in the US in the form of the FDIC and related entities (including Federal Reserve supervision and the OCC). This is largely because market-based regulation of banks by private deposit insurers (such as by allowing insurers to cancel coverage if banks breach certain risk limits) would be difficult (at best) to structure without the broad legal authority the government has to seize control of an institution that breaches risk limits and make necessary changes. If private deposit insurers can't rescind coverage, their ability to discipline banks is limited; if they can, then banks face a likely run if their coverage is rescinded, which solves nothing. It is also, of course, difficult as a practical matter because of the aforementioned opacity of bank balance sheets.
Fourth and finally, as discussed by Caballero (2009a, 2009b), bank failures don't occur in isolation; institutions tend to be impaired at exactly the same moment that other institutions and markets are impaired. While you correctly note that a form of partial insurance is in use (in the form of credit-default swaps) today, it's worth considering what happened during the crisis, when outstanding CDS contracts caused the failure of the insurer AIG.
This leads us to a reasonable question: what would a private deposit insurer look like? We know at least two things. One, it would have to be very well-capitalized, for if it were not, the Diamond-Dybvig "run" equilibrium would still exist. Two, it would have to hold its significant reserves in the form of information-insensitive "safe" assets, most likely government-guaranteed securities, or else it may not be able to liquidate those assets under the conditions that lead to bank failures (which can be accompanied by fire sales and other phenomena that impair asset values).
This leads us to an answer to your second question, which is yes, this would be relatively expensive, as you'd have to insure the whole stack of deposits, rather than allowing the government to provide a tail risk guarantee as it does with the Deposit Insurance Fund (if the FDIC's DIF is run to zero during a crisis, the US government will make up the difference). That tail risk guarantee provided by the government is a conditional put— it costs nothing until the DIF needs a bailout, at which point the government can fund it by issuing debt at the very low rates that prevail (for safe assets) during times of financial distress.
To answer your third question, the DIF has never required a bailout, and its rates are adjusted to prevent it from holding reserves that are too great, so— the FDIC is probably charging an actuarially fair rate over a long time horizon, though the rate may be too high or too low at certain points in time.