There are already a lot of answers to this question, but I haven't seen the following information:
The money that you pay for private health insurance includes a contribution towards making your health insurance cheaper in old age. This is mandatory for German private health insurances. So German private health insurances are not really comparable to the international, truly free market insurances. The latter are very cheap when you are young and healthy, and rise a lot as you get older and sicker. German private insurances are a lot more stable in price (mine actually fell by a few cents last year for example, not counting no-claims bonuses).
On top of this mandatory government scheme for trying to keep your health insurance costs down, a small number of German private health insurance providers also offer their own schemes for keeping costs down as you get older.
The amount you pay into these schemes varies according to how old you are, but a rough estimate that I was given, involved paying 200 euros per month on top of my health insurance now, and getting 400 euros per month back when I'm over 60.
I was told that this, together with the mandatory government scheme, would mean that my health insurance costs would drop to almost zero when I'm 60.
I mention this quote only to give you an idea of what's available. Of course, you need to speak to agents from several private health insurances, who can explain your options in detail.
Don't be shy about asking for an agent who speaks good English. However good your German is, insurance is full of small details that may be easier to absorb in your native language. German financial products are not always the same as what is offered in other countries, so you really need to take time to understand them well.
Unfortunately, many immigrants are forced to make the private/public health insurance choice before they are really well-informed.