The Internet of Vehicles (IoV) enables data exchange among individuals, cloud resources, road infrastructures, and vehicles, interconnected through Vehicular Ad Hoc Networks (VANETs). VANETs comprise vehicles with Onboard Units (OBUs), Roadside Units (RSUs), and a Trusted Party Agent (TPA). The data transmission among these entities supports seamless interaction and collaborative traffic management. However, data transmission on public communication channels in VANETs presents significant challenges, including security, privacy, and authentication of participating entities. Although numerous key exchange and authentication protocols have been introduced to tackle these issues, many protocols remain vulnerable to various attacks, such as a vehicle, RSU, TPA impersonation, denial of service, physical cloning, and desynchronization attacks. Therefore, to address these vulnerabilities, we propose a key exchange protocol that leverages hash functions and Advanced Encryption Standard (AES) encryption. Our protocol also integrates the Physical Unclonable Function (PUF), enhancing its resistance to physical or cloning attacks. Additionally, it effectively counters threats like impersonation, session key leakage, ephemeral secret leakage, and desynchronization attacks. We validate the security and reliability of our protocol through both formal and informal analysis. Informal analysis highlights the protocol’s essential security features, while formal analysis provides robust substantiation. Performance evaluation reveals that our protocol achieves an average reduction of 35.53%, and 53.77%, in communication and computation overheads.