While the emerging vehicle-to-everything (V2X) connectivity paradigm is radically transforming the automotive sector, unprecedented security challenges arise, calling for innovative security enablers with minimum impact on the ongoing communication. In dense V2X scenarios, the 5G authentication and key agreement (5G-AKA) procedure may suffer from uncontrolled failures which result in unacceptable latency levels due to the excessive signalling overhead. In this paper, we introduce a lightweight vehicle authentication scheme, as an extension of the 5G-AKA, to adequately address a high number of authentication requests. The proposed mechanism leverages the space-efficient features of the cuckoo filter, a probabilistic data structure for approximate set membership tests, to achieve authentication of multiple vehicles at a time. Our performance analysis reveals the impact of various cuckoo filter parameter configurations on the authentication efficiency. In addition, our proposed authentication mechanism is able to outperform the standardized 5G-AKA procedure in terms of latency and protocol overhead even for high vehicle load. ; Grant numbers : SPOT5G - Single Point of attachment communications heterogeneous mobile data networks (TEC2017-87456-P), INSPIRE-5Gplus - INSPIRE-5Gplus INtelligent Security and Pervasive tRust for 5G and Beyond and FIREMAN - Framework for the Identification of Rare Events via MAchine learning and IoT Networks projects.© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.