> If you want replay protection it's probably sufficient to either remember used keys or add a timestamp.

The replay Filippo is talking about is in the context of a single key. The remote side simply reads the nonce || message off the wire and aead.Opens it, without regard to whether or not that nonce has been used before to decrypt a previous message.