You could use another key derivation function such as scrypt or pbkdf2+sha2 (or sha3).
Although I think this approach to authentication is very wasteful of both bandwidth, memory and CPU and to top it off its less secure. In order for key stretching to be effective, it must be heavy, and you'll need to make this calculation for every request. I think you are better off issuing a cryptographic nonce, and back the server state with a fast non-relational database like memcachd. Sure its not "RESTful", but its a more efficent and a more secure design.
The best cryptographers use cryptography when there is no other choice. Plan on failure.