Operational and security requirements for RFID systems such as system scalability, anonymity and anti-cloning are difficult to obtain due to constraints in area, memory, etc. Due to scarceness of resources most of the proposed protocols were designed using symmetric key cryptographic algorithms. However, it has been shown that it is inevitable to use public-key cryptographic algorithms to satisfy these requirements [1]. Moreover, general public-key cryptography based authentication protocols are vulnerable in terms of anonymity, which is shown in this paper. Accordingly, we design a new authentication protocol named EC-RAC using EC (Elliptic Curve) cryptography. EC-RAC can be proved for its security in the generic group model and is carefully designed to minimize its computational workload. Moreover, we present the implementation results of EC-RAC to show its feasibility for RFID systems.