Currently, the distributed Internet of vehicle (DIoV) of smart city leverages the transmitted messages form the distributed network servers and vehicles, and so effectively enables the prompt DIoV’s service, e.g., vehicle travel and accident rescue. However, in the open communication channel of DIoV, those important or invaluable transmitted messages in DIoV are vulnerable to illegal access or even manipulation. Therefore, a reliable and secure message authentication protocol is a necessary condition to ensure the services of distributed vehicular networks. Moreover, most of the existing authentication schemes cannot effectively resist various network attacks, which greatly reduces the security of vehicular communication. In this work, we propose a secure and efficient distributed authentication and key agreement protocol for securing the communication in DIoV. The vehicles can authenticate each other and establish session keys through pre-shared keys. In addition, our scheme can realize the function of vehicle joining and leaving the network without frequently updating the network key. Through heuristic analysis and BAN logic analysis, the security of the scheme is proved. Compared with the existing schemes, the proposed scheme satisfies the security requirements and has obvious advantages in computing and communication overhead.