In one embodiment, an authenticator in a communication network maintains a persistent authenticator epoch value that increments each time the authenticator restarts. The authenticator also maintains a persistent per-supplicant value for each supplicant of the authenticator, each per-supplicant value set to a current value of the authenticator epoch value each time the corresponding supplicant establishes a new security association with the authenticator. To communicate messages from the authenticator to a particular supplicant, each message uses a per-supplicant replay counter having a security association epoch counter and a message counter specific to the particular supplicant. In particular, the security association epoch counter for each message is set as a difference between the authenticator epoch value and the per-supplicant value for the particular supplicant when the message is communicated, while the message counter is incremented for each message communicated.