The host identity protocol (HIP) has emerged as the most suitable solution to uniquely identify smart devices in the mobile and distributed Internet-of-Things (IoT) systems, such as smart cities, homes, cars, and healthcare. The HIP provides authentication methods that enable secure communications between HIP peers. However, the authentication methods provided by the HIP cannot be adopted by the IoT devices with limited processing power because of the computation-intensive cryptographic operations involved in hash generation, signature validation, and session-key establishment. Moreover, IoT devices cannot utilize the HIP as is to communicate securely in the low power and lossy networks as there is a considerable communication overhead, such as packet fragmentation and reassembly, for exchanging certificates over a lossy link. Additionally, the use of static host identifiers makes IoT devices vulnerable to cyber espionage and user-Targeted attacks. In this article, we propose an authentication scheme, P-HIP, that protects the identity privacy of an IoT device by enabling the device to compute and use unique host identifiers from networks to networks and sessions to sessions. To make the HIP suitable for resource-constrained IoT devices, P-HIP provides methods that unburden IoT devices from computation-intensive operations, such as modular exponentiation, involved in authentication and session-key exchange. Additionally, P-HIP minimizes the communication overheads for exchanging certificates in lossy networks. We implement a prototype of P-HIP on Contiki-enabled IoT that shows P-HIP can reduce computation costs, communication overheads, and the session-key establishment time when used by low-powered devices in a lossy network.