Remote user authentication has found numerous real-world applications, especially in a user-server model. In this work, we introduce the notion of anonymous remote user authentication with k-times untraceability (k-RUA) for a given parameter k, where authorized users authenticate themselves to an authority (typically a server) in an anonymous and k-times untraceable manner. We define the formal security models for a generic k-RUA construction that guarantees user authenticity, anonymity and user privacy. We provide a concrete instantiation of k-RUA having the following properties: (1) a third party cannot impersonate an authorized user by producing valid transcripts for the user while conversing during a session; (2) a third party having access to the communication channel between the user and the authority cannot identify the session participants; (3) the authority can trace the real identities of dishonest users who have authenticated themselves for more than k times; (4) our k-RUA construction avoids using expensive pairing operations—which makes it efficient and suitable for devices having limited amount of computational resources.