One of the significant services provided by IoV in Smart cities is vehicular navigation. Drivers often find it difficult and time-consuming to complete their trip in a crowded city without real-time knowledge about the traffic and road conditions. So, a proper routing mechanism can help drivers reach their destination in minimum time and with less fuel consumption. However, it has been found that such protocols often face security challenges. In this paper, we have proposed an authenticated navigation scheme with the help of pseudonym-based asymmetric-key cryptography that discovers and secures the route to the destination in real time. The architecture embodies a geolocation provider (GLP) to get the possible static routes to a particular destination. Further, it uses the message-forwarding capability of RSUs to develop a dynamic route, after receiving feedback from the respective RSUs about the traffic conditions. While doing so, this protocol ensures proper message integrity, anonymity, unlinkability and robust protection from important security threats. Our approach ensures minimal end-to-end delay and efficient real-time route finding from a source to a destination with no extra overhead on the vehicles. We have simulated our authentication protocol using the Scyther simulator and found it safe from various adversarial attacks.