Connected and Autonomous vehicles stand to drastically improve the safety and efficiency of the transportation system in the near future while also reducing pollution. These systems leverage communication to coordinate among vehicles and infrastructure in service of a number of safety and efficiency driver assist and even fully autonomous applications. Attackers can compromise these systems in a number of ways including by falsifying communication messages, making it critical to support security mechanisms that can operate and scale in dynamic scenarios. Towards this end, we present TVSS, a new VPKI system which improves drastically over prior work in the area (including over SCMS; the US department of transportation standard for VPKI). TVSS leverages the idea of unforgeable tokens to enable rapid verification at the road side units (RSUs), which are part of the road infrastructure at the edge of the network. This edge based solution enables agile authentication by avoiding the need for back-end servers during the potentially short contact time between a moving vehicle and the infrastructure. It also results in several security advantages: (1) Scalable Revocation: it greatly simplifies the revocation problem, a difficult problem in large scale certificate systems; and (2) Faster Refresh: Vehicles interact more frequently with the system to refresh their credentials, improving the privacy of the system. We provide a construction of the system and formally prove its security. Field experiments on a test-bed we develop consisting of on-board units (OBUs) and RSUs shows substantial reduction in the latency of refreshing credentials compared to SCMS, allowing the system to work even with smaller window of connectivity when vehicles are moving at higher speeds. Notably, we are able to execute the bottleneck operation of our scheme with a stationary RSU while traveling at highway speeds .