Communication messages in Vehicular Ad-hoc Networks (VANETs) can be used to track movement of vehicles. In this paper, we address the problem of movement tracking and enhance location privacy without affecting security and safety of vehicles. By considering unique characteristics of VANETs, we firstly propose a synchronized pseudonym changing protocol based on the concept of forming groups among neighboring vehicles. Secondly, we analytically evaluate the anonymity and unlinkability of the proposed protocol. Finally, we do a series of simulations to evaluate the performance of our protocol in real VANET environments such as Manhattan and Urban. Simulation results show that our protocol is feasible and produces excellent performances. The main advantages of our protocol compared with the existing approaches include: 1) it makes larger anonymity set and higher entropy; 2) it reduces the tracking probability; 3) it can be used in both safety and non-safety communications; and 4) Vehicles need not suspend regular communication for changing pseudonyms.