Electric vehicles (EVs) are gaining popularity due to the growing awareness for a sustainable future. However, since there are disproportionately fewer charging stations than EVs, range anxiety plays a major role in the rise in the number of queries made along the journeys to find an available charging station. On the other hand, the use of personal data in various types of analytics is increasing at an unprecedented rate. Hence, the risks of privacy violation are also surging. Geo-indistinguishability is one of the standards for formalising location privacy as a generalisation of the local differential privacy. However, the noise has to be carefully calibrated considering the implications of potential utility-loss. In this paper, we introduce approximate geo-indistinguishability (AGeoI) which allows the EVs to obfuscate the individual query-locations while ensuring that they remain within their preferred area of interest. It is vital because journeys are often sensitive to a sharp drop in QoS, which has a high cost for the extra distance to be covered. We apply AGeoI and dummy data generation to protect the privacy of EVs during their journeys and preserve the QoS. Analytical insights and experiments are used to demonstrate that a very high percentage of EVs get privacy for free and that the utility-loss caused by the privacy-gain is minuscule. Using the iterative Bayesian update, our method allows for a private and highly accurate prediction of charging station occupancy without disclosing query locations and vehicle trajectories, which is vital in unprecedented traffic congestion scenarios and efficient route-planning.