5G technology is called to support the next generation of wireless communications and realize the “Internet of Everything” through its mMTC (massive Machine-Type-Communications) service. The recently standardized 5G-AKA protocol is intended to deal with security and privacy issues detected in earlier generations. Nevertheless, several 5G-AKA shortcomings have been reported, including a possibly excessive computational complexity for many IoT devices. To address these, a promising lightweight 2-pass authentication and key agreement (AKA) protocol for 5G mobile communications has recently been proposed by Braeken. Compared to the 5G-AKA protocol, this does not require the use of public key encryption. This paper analyzes the security claims of Braeken’s protocol and shows that it does not provide full unlinkability, but only session unlinkability, and is (still) subject to Linkability of AKA Failure Messages (LFM) attacks. We propose solutions to such problems and prove that symmetric-key based protocols cannot offer higher privacy protection levels without compromising availability. We then describe an enhanced version of this protocol that addresses these vulnerabilities and supports forward secrecy, which is a desirable feature for low-cost IoT devices.