Traditional key pre-distribution schemes in sensor and ad hoc networks rely on the existence of a trusted third party to generate and distribute a key pool. The assumption of a single TTP however can be very strong in practice, especially when nodes belong to different domains and they come together in an ad hoc manner. Other important motivations to omit a TTP include preservation of privacy in a network as well as reducing the required knowledge base for the usage of sensor networks. In this work, we show the shortcomings of the previous approaches [3, 13] in terms of both efficiency and security. By incorporating a heterogeneous network, we show that we can dramatically reduce the load on resource constrained devices while also increasing their security. We also propose a new strengthened security model for self-organized ad hoc networks and evaluate the security of our protocol in this model. We evaluate the correctness of the protocol and show that we can achieve network connectivity with very high probability.