The Internet of Vehicles (IoV) can significantly improve transportation efficiency and ensure traffic safety. Authentication is regarded as the fundamental defense line against attacks in IoV. However, the state-of-the-art approaches suffer from several drawbacks, including bottlenecks of the single cloud server model, high computational overhead of operations, excessive trust in cloud servers and roadside units (RSUs), and leakage of vehicle trajectory privacy. In this paper, BEPHAP, a Blockchain-based Efficient Privacy-preserving Handover Authentication Protocol with key agreement for internet of vehicles, is introduced to address these problems. BEPHAP achieves anonymous cross-domain mutual handover authentication with key agreement based on the tamper-proof blockchain, symmetric cryptography, and the chameleon hash function under a security model that cloud servers and RSUs may launch attacks. BEPHAP is particularly well suited for IoV since it allows vehicles only need to perform lightweight cryptographic operations during the authentication phase. BEPHAP also achieves data confidentiality, unlinkability, traceability, non-repudiation, non-frameability, and key escrow freeness. Formal verification based on ProVerif and formal security proofs based on the BAN logic indicates that BEPHAP is resistant to various typical attacks, such as man-in-the-middle attacks, impersonation attacks, and replay attacks. Performance analysis demonstrates that BEPHAP surpasses existing works in both computation and communication efficiencies. And the message loss rate remains 0 at 5000 requests per second, which meets the requirement of IoV.