A server device initiates a traffic encapsulation key (TEK) re-key sequence for a group virtual private network (VPN), based on an upcoming expiration time for an existing TEK. The server device sends, via a push message during a first time period immediately after the initiating, a new TEK to members of the group VPN. The server device receives, during a second time period that immediately follows the first time period, a pull request, for the new TEK, from one of the members of the group VPN, and sends, to the one of the members, the new TEK, where the re-key sequence transitions all the members of the group VPN from the existing TEK key to the new TEK key before the expiration time for the existing TEK.