A VPN establishes a cryptographically secure network using the existing insecure infra structure of the Internet. A number of protocols, including IPSec have been designed to establish VPNs. However, keys must be shared between the communicating peers before a VPN can be established. IKE protocol is used for exchanging keys between authenticated peers over the Internet. However, IKE is vulnerable to DoS attacks and has security holes. A number of protocols have been proposed to replace IKE but these protocols also have vulnerabilities of their own. In this paper we present an analysis of IKE and identify its security holes and design weaknesses. We also propose a more secure and efficient key exchange protocol, Arcanum, and carry out its security analysis and comparison with existing protocols. Arcanum is more secure, robust to DoS attacks and efficient in terms of time and number of messages.