Geographic information like location data is essential for a smart health care system. Patient information data is periodically sent to hospitals or medical centers to improve healthcare services presented to patients. The location data with a timestamp can disclose the user's private data like user financial activity, medical status, lifestyle, and places frequently visited by the user. Privacy protection approaches include spatial cloaking that is used to conceal the location of the user, into a cloaking area that satisfies the user privacy requirement when using the location to get healthcare services, or when using location-based services (LBS) to get any other services. Spatial cloaking is used in many location privacy solutions, however, most of them have some disadvantages that are related to communication and computation costs. In this paper an effective spatial cloaking algorithm to preserve location privacy (LOCACY) is presented. A secure version of the A* heuristic search algorithm (SecA*) has been developed to perform two essential functions: the first is to better support the proposed spatial cloaking algorithm, and the second is to enable a mobile patient to avoid infected areas while traveling between various locations. The proposed spatial cloaking algorithm outperforms rival algorithms such as bottom-up, top-down, and Aman algorithms in terms of communication and computation costs and achieves average enhancement of 56% better than the recently proposed Aman algorithm. Evaluating the secure A* algorithm shows that it provides a safe path and improves the provision of privacy.