First and second nested virtual private networks share a common rekey service. A first key server generates first cryptographic keys and policies for use by gateways of the VPN to encrypt and decrypt data packets. The key server establishes a connection with a second key server to generate second cryptographic keys and policies independently of the first key server for use by encryption units of a second VPN that is nested with and operates independently of the first VPN. The first key server refreshes the first cryptographic keys in the first VPN gateways using a common rekey service, and cooperates with the second key server to refresh the second cryptographic keys in the second VPN encryption units using the common rekey service.