RSEAP is a recently proposed RFID based authentication protocol for vehicular cloud computing whose authors claimed to be secure and efficient. In this article, we challenge these claims. More precisely, we show that RSEAP does not provide the desired security, and it is possible to conduct both tag and reader impersonation attacks efficiently. Besides, despite the use of timestamps, we show how this protocol also suffers from a range of relay attacks. The complexity of any of the proposed attacks is negligible while the success probability is maximum (i.e., the adversary's success probability is '1' since all the proposed attacks are deterministic). To improve the security of RSEAP scheme, we suggest the required patches for fixing the security vulnerabilities mentioned above. We show that the improved protocol, called RSEAP2, is more efficient (computation and communication costs) than the original RSEAP, while provides a higher security level. The security of RSEAP2 is evaluated informally and also formally using the Scyther tool, which is a well-known and automated tool to assess the security of cryptographic protocols. Additionally, we have formally verified the security of the proposed scheme under the Real-or-Random oracle model.