Virtual Private Networks have been efficient tools that provide inter-connectivity to exchange information between different (remote) parties that belong to a specific network. A virtual private network possesses all the features of the private networks and are built upon existing network, but they suffer severe security problems, particularly, the authentication problem. In this paper we propose a new model for the VPN based on certificateless cryptography to authenticate users and establish a secure session between them. The new model solves the PKI problems of the certificates management in the VPNs.