You can use the EEPROM to save the current ID.
it has limits if 100,000 writes, you can use techniques similar to what SSD's use to spread the data over the eeprom rather than burning out one cell. You could get millions of writes this way.
Even better, use another hashing algorithm and say an RTC module on the Arduino.
Create a block of data repeating the time from the RTC, then hash it.
Then use this as an ID, it will be unique. For security, its non sequential and does not need to be stored.
The purpose of this style of ID is to provide validation of a single message, not to identify it in a pool of messages. As in it has no meaning to the data, just the hash cannot be created without it.
If the system dies, no worries just set the time and the unique ID's are restored.
There is nothing stopping someone creating their own data to send, as a sequential message is just as easy to beat as a hash, its all down to AES having a secure key.
Packages like SSL and Kerberos gain their security by making a shared key's lifetime as short as possible. Literally the only thing going for them is the fact it takes so long to brute force an algorithm., by constantly changing the key ( or IV ) it means you have to restart the brute force and also limits the amount of data encrypted to a single key you can grab. Once the encryption algo is broken the TLS is useless.