Methods of operating a user equipment (UE) in a mobile communication network are disclosed. An authentication process start message may be transmitted from the UE to the mobile communication network, wherein the authentication process start message includes an identifier for the UE. After transmitting the authentication process start message from the UE, a request commit message may be received from the mobile communication network. Responsive to receiving the request commit message, a response commit message may be transmitted to the mobile communication network. After transmitting the response commit message, an authentication challenge message may be received corresponding to the authentication process start message. Related methods of operating network nodes are also discussed.