removing the ability of private health insurance companies to compete will give rise to a natural monopoly in the industry, leading to an overall increased cost to the taxpayer.
Emphasis mine - and this is where the free-market assumption is utterly wrong.
Private health insurance, private hospitals, and private everything has one focus in mind. Return on investment. Not whether you get better. Not whether your treatment is effective. Not whether your treatment is cost-effective. Solely whether the organisation can turn a profit. This is the focus of every individual in that organisation, from the CEO to the cleaners. In a private system, your doctor does not care about you - they care about the money they can make from you. I'm not saying that everyone working in private medicine are inherently bad people. But I am saying their job does not allow them to be a good person at work.
So the most important thing in treating a patient is how to make the biggest profit from that patient. If we assume the cost of treatment is identical (and that in itself is a bad assumption; the UK's NHS pays an order of magnitude less for the same drugs compared to US hospitals), then the only way to increase your profit is to charge more for treatment.
If there was a way to shop around for treatment, then costs would certainly come down through competition. This is actually true for many elective procedures such as plastic surgery, hip replacements, and other non-emergency procedures.
But when it comes to an emergency, there is no competition. The ambulance picks you up from your car crash, unconscious, and takes you to the nearest hospital. You can't shop around. And you don't even know how much you owe until you recover from surgery.
So there is already a "natural monopoly" for emergency medical care, and the monopolists are maximising their return on their monopoly to the profound detriment of their customers/victims. And as with any other de-facto monopoly, the only way to control this exploitation is either with regulation or with nationalisation in the public interest. In every other monopoly situation in the past, this has resulted in lower costs to the consumer.
Which leads on to your actual question...
Why isn't competition between health insurance providers lowering the cost of premiums?
When the private healthcare providers can essentially charge what they like as monopolists, those costs are borne by the patient. If the patient has health insurance, then those costs are passed on to the insurer (less any co-pay amount, of course).
The insurer is therefore just as much a victim of the monopoly as the patient. They have no ability to limit how much a healthcare provider can charge. In order to pay these inflated costs, the only thing an insurer can do is raise premiums for all their customers.
A healthcare provider will charge the same amount per procedure to everyone - and since insurers will all have a similar customer base, they will all have to deal with similar costs from providers. So it follows that insurers will all have to charge very similar premiums, because they are all paying the same inflated costs to monopoly healthcare providers. If the healthcare provider puts up their costs, every insurer has to raise their prices correspondingly. This eliminates the possibility of competition between insurers, because the insurers themselves have no ability to affect costs.
The only possible source of competition amongst insurers would be to screen patients on application. Patients assessed as lower risk could be given lower premiums, because on average they will not have such high healthcare costs; and vice versa, higher risk patients would have higher premiums; and if an event occurs (such as a cancer diagnosis) which would increase risk then the next premium would be increased. This is widely seen as an unfair system, because it penalises people for factors (such as cancer) beyond their control. It is therefore illegal in some places.