Techniques are presented for optimizing secure communications in a network. As disclosed herein, a key server is configured to provision a plurality of routers that are part of a virtual private network. The key server selects a counter value that is part of a security association and calculates a key value. The key server sends the key value, together with the security association, to the plurality of routers that are part of the virtual private network to enable them to exchange encrypted packets with each other in the virtual private network using the key value and the security association. The key server then increments the counter value to a value within a range of counter values capable of being predicted by the plurality of routers that received the key value.