Electric vehicles (EVs) have been slowly replacing conventional fuel based vehicles since the last decade. EVs are not only environment-friendly but when used in conjunction with a smart grid, also open up new possibilities and a Vehicle-Smart Grid ecosystem, commonly called V2G can be achieved. This would not only encourage people to switch to environment-friendly EVs or Plug-in Hybrid Electric Vehicles (PHEVs), but also positively aid in load management on the power grid, and present new economic benefits to all the entities involved in such an ecosystem. Nonetheless, privacy and security remains a serious concern of smart grids. The devices used in V2G are tiny, inexpensive, and resource constrained, which renders them susceptible to multiple attacks. Any protocol designed for V2G systems must be secure, lightweight, and must protect the privacy of the vehicle owner. Since EVs and charging stations are generally not guarded by people, physical security is also a must. To tackle these issues, we propose Physical Unclonable Functions (PUF) based Secure User Key-Exchange Authentication (SUKA) protocol for V2G systems. The proposed protocol uses PUFs to achieve a two-step mutual authentication between an EV and the Grid Server. It is lightweight, secure, and privacy preserving. Simulations show that the proposed protocol performs better and provides more security features than state-of-the-art V2G authentication protocols. The security of the proposed protocol is shown using a formal security model and analysis.