The Intelligent Transportation System (ITS) and Internet of Things (IoT) technologies have facilitated the rapid development of Vehicular Ad-hoc Networks (VANETs) in recent years. There have been attempts to integrate edge computing into VANETs, but it is difficult to design efficient and secure authentication schemes due to reasons such as potential security attacks and long authentication delays caused by the high-speed mobility of vehicles. Most of the existing authentication protocols either do not consider attacks such as anonymous linking of real vehicle identities within the network or do not provide effective methods to ensure user request privacy. To address the above issues, we designed an Edge-Assisted Authentication Key Agreement (EA-AKA) protocol, which achieves secure authentication and generates a secure agreed session key for secret communication. Through the Tesla broadcast protocol, edge nodes help vehicles generate dynamic anonymity to ensure untraceability. After mutual authentication, an enhanced blind signature is utilized to ensure the privacy of vehicle users’ requests. The security analysis confirms that the scheme fulfills the security requirements in VANETs. Furthermore, our scheme demonstrates improved performance in computing and communication efficiency.