The mechanisms adopted by cellular technologies for user identification allow an adversary to collect information about individuals and track their movements within the network; and thus exposing privacy of the users to unknown risks. Efforts have been made toward enhancing privacy preserving capabilities in cellular technologies, culminating in Long Term Evolution LTE technology. LTE security architecture is substantially enhanced comparing with its predecessors 2G and 3G; however, LTE does not eliminate the possibility of user privacy attacks. LTE is still vulnerable to user identity privacy attacks. This paper includes an evaluation of LTE security architecture and proposes a security solution for the enhancement of user identity privacy in LTE. The solution is based on introducing of pseudonyms that replace the user permanent identifier (IMSI) used for identification. The scheme provides secure and effective identity management in respect to the protection of user privacy in LTE. The scheme is formally verified using proVerif and proved to provide an adequate assurance of user identity privacy protection.