Due to the dire consequences of privacy abuse in vehicular ad hoc network (VANET), a number of mechanisms have been put forth to conditionally preserve the user and location privacy. To date, multiple pseudonymous approach is regarded as one of the best effective solutions where every node uses multiple temporary pseudonyms. However, recently it has been found out that even multiple pseudonyms could be linked to each other and to a single node thereby jeopardizing the privacy. Therefore in this paper, we propose a novel identity exchange-based approach to preserve user privacy in VANET where a node exchanges its pseudonyms with the neighbors and uses both its own and neighbors' pseudonym randomly to preserve privacy. Additionally the revocation of the immediate user of the pseudonym is made possible through an efficient revocation mechanism. Moreover the pseudonym exchange is realized through covert communication where a side channel is used to establish a covert communication path between the exchanging nodes, based on the scheduled beacons. Our proposed scheme is secure, robust, and it preserves privacy through the existing beacon infrastructure.