We address the decades-old privacy problem of disclosure of the permanent subscriber identity (IMSI) that makes IMSI catchers a real threat to all generations of mobile networks. A number of possible modifications to existing protocols have been proposed to address the problem; however, most require significant changes to existing deployed infrastructures. We propose a novel authentication approach for 3G and 4G systems that does not affect intermediate entities, notably the serving network and mobile equipment. It prevents disclosure of the subscriber's IMSI by using a dynamic pseudo-IMSI that is only identifiable by the home network for the USIM. A major challenge in using dynamic pseudo-IMSIs is possible loss of identity synchronisation between USIM and home network, an issue that has not been adequately addressed in previous work. We present an approach for identity recovery to be used in the event of pseudo-IMSI desynchronisation. The scheme requires changes to the home network and the USIM, but not to the serving network, mobile phone or other internal network protocols, enabling simple, transparent and evolutionary migration. We provide a detailed analysis of the scheme, and verify its correctness and security properties using ProVerif.