Lawful Interception (LI) is a legal obligation of Communication Service Providers (CSPs) to provide interception capabilities to Law Enforcement Agencies (LEAs) in order to gain insightful data from network communications for criminal proceedings, e.g., network identifiers for tracking suspects. With the privacy-enhancements of network identifiers in the 5th generation of mobile networks (5G), LEAs need to interact with CSPs for network identifier resolution. This raises new privacy issues, as untrusted CSPs are able to infer sensitive information about ongoing investigations, e.g., the identities of their subscribers under suspicion. In this work, we propose P3LI5, a novel system that enables LEAs to privately query CSPs for network identifier resolution leveraging on an information retrieval protocol, SparseWPIR, that is based on private information retrieval and its weakly private version. As such, P3LI5 can be adapted to various operational scenarios with different confidentiality or latency requirements, by selectively allowing a bounded information leakage for improved performance. We implement P3LI5 on the 5G LI infrastructure using well known open-source projects and demonstrate its scalability to large databases while retaining low latency. To the best of our knowledge, P3LI5 is the first proposal for addressing the privacy issues raised by the mandatory requirement for LI on the 5G core network.