You could always some form of SRP[0]. It shouldn't be too much overhead to do only when your session times out. At the very least you're 1) not sharing secrets 2) limits reply attacks to a finite amount of time.

The other method might be, as a sibling said, HMAC the message with a shared private key. If you can specify that clocks should be pretty close, your reply attack window becomes small.

[0]: http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol