How can I prevent a message replay with RSA?
You could use some combination of:


an expiration timeout (i.e. if the message does not arrive until the timeout, we don't accept it)
storing previous values of a nonce.


You only have to store those nonce values whose timeout didn't yet expire.

If the messages arrive all in order, you can instead use a simple counter (which always goes up) and reject every message which has a counter value smaller or equal than the last received one.