Identity Based Cryptography (IBC) is well known method in the field of security, however it has an inherent drawback of Key Escrow under which central key generation center is a sole issuing authority of private key and thus could misuse it. Our survey finds numerous solutions of key escrow; out of them secure key issuing protocol (SKIP) is most prominent. However, there are scopes for improving communication efficiency of this protocol. Thus, we propose an improved version of this protocol by employing clustering approach. With theoretical and empirical analysis, we demonstrate that the proposed approach indeed effectively reduces the communication overheads and improves efficiency of the original secure key issuing protocol.