With the democratization of mobile devices embedding different positioning capabilities, location information is used for a variety of applications. On mobile devices, the geolocation can be obtained via GPS or by leveraging surrounding network infrastructure such as Wi-Fi access points. Despite a lower accuracy, Wi-Fi based geolocation has several advantages over GPS such as reduced energy consumption and availability in indoor environments. To enable this network-based geolocation, mobile devices need to interact with a location positioning system that will resolve a list of visible Wi-Fi access points into a position. By doing so, mobile users are revealing their mobility to the location provider, potentially exposing sensitive information to an untrusted third-party. In this paper, we propose a novel solution to preserve users' privacy when requesting users' location from Wi-Fi while supporting high utility. The key idea behind our online approach is to combine a caching strategy (for limiting the exposure of the user's position for already visited locations) and a random sampling (for controlling the precision of revealed information). We extensively evaluate our solution with a real dataset of mobility traces. We show that the proposed approach drastically reduces the exposure of the user's location to positioning systems (up to 95%). Indeed, by leveraging a caching strategy, requests are only sent when users visit new areas. Consequently, the capacity of positioning systems to infer points of interest of users from received requests is highly limited (a decrease of 50% on average). In addition, our privacy protection provides a trade-off between privacy (i.e., avoid revealing its true location) and utility (i.e., still benefiting from services such as places recommendation) fully controllable by the users.