The rapid progression of Vehicular Ad-Hoc Networks (VANETs) has greatly eased the dissemination of safety-critical data among vehicles. However, the susceptibility of wireless links in VANETs to malicious attacks presents a significant obstacle. To mitigate the obstacle, various authenticated key agreement (AKA) schemes have been devised to establish secure communication between vehicles and infrastructure. However, the advent of quantum computing threatens the security of traditional number theory-based AKA schemes. As a countermeasure, lattice-based schemes have emerged, offering quantum resistance. However, many such lattice-based schemes incur high computational and communication overhead. To overcome these limitations, this paper proposes an efficient and provably secure lattice-based AKA scheme for VANETs. Devised AKA protocol leverages quantum-safe lattice-based cryptography to ensure communication security between vehicles and infrastructure. A comprehensive security analysis within the Real-or-Random model framework validates the proposed scheme’s robustness. Furthermore, performance analysis shows that the proposed scheme reduces computational cost by approximately 92% and communication cost by 29% compared to the existing recent approach, making it well-suited for VANET deployment.