In Europe, airlines pay so-called route charges for flying through national airspaces. EUROCONTROL, the European aviation organisation, collects route charges from their Central Route Charges Office, CRCO, and then distributes the money to the member states, who in turn will distribute them to the national air navigation service providers (ANSP's) - including private ones. The advantage of collecting route charges centrally, is that airlines only have to pay to a single organisation, in a single currency.
The charge for individual flights is calculated based on distance flown and aircraft weight, which are multiplied by a unit rate. The unit rates are determined by the individual countries - they are not the same across all of Europe. Unit rates are based on the actual costs for providing air traffic services, such as ATC, communication facilities, navigation equipment, meteorological information, aeronautical information service and so on.
Route charges do not apply to aircraft weighing less than 2 tonnes, state and government flights and search and rescue flights. Some states also exempt military flights, training flights, test flights, local flights, VFR flights, humanitarian flights, police flights etc.
You can read more about the CRCO here, and about how route charges are determined here.
Regarding your second question, I fail to see why a private ANSP should be any less safe than a government one.