An efficient and secure mobile IP registration protocol is proposed, which is based on certificateless public key signature scheme without pairing to minimize the registration time. Vser anonymity is achieved via the temporary identity (TID) transmitted by the mobile user, instead of the true identity. Additional replay protection is included by introducing Nonce in the registration message to prevent a possible replay attack. Security analyses demonstrate that the new scheme is both secure and efficient. Numerical experimental results and security performance analyses show that the new scheme outperforms the existing ones regarding the registration time and computational load while improving security.