Until quite recently, anonymous credentials systems were based on public key primitives. A new approach, that relies on algebraic Message Authentication Codes (MACs) in prime-order groups, has recently been introduced by Chase et al. at CCS 2014. They proposed two anonymous credentials systems referred to as "Keyed-Verification Anonymous Credentials (KVAC)" as they require the verifier to know the issuer secret key. Unfortunately, both systems presentation proof, for n unrevealed attributes, is of complexity O(n) in the number of group elements. In this paper, we propose a new KVAC system that provides multi-show unlinkability of credentials and is of complexity O(1) in the number of group elements while being almost as efficient as Microsoft's U-Prove anonymous credentials system (which does not ensure multi-show unlinkability) and many times faster than IBM's Idemix. Our credentials are constructed based on a new algebraic MAC scheme which is of independent interest. Through slight modifications on the verifier side, our KVAC system, which is proven secure in the random oracle model, can be easily turned into a public-key credentials system. By implementing it on a standard NFC SIM card, we show its efficiency and suitability for real-world use cases and constrained devices. In particular, a credential presentation, with 3 attributes, can be performed in only 88 ms.