How to Implement Simple, Quick HMAC on Arduino
I ended finding a Arduino library called Spritz which can be found here:
https://github.com/abderraouf-adjal/ArduinoSpritzCipher

Also, for anyone else who comes across this task, here is a very simple Hashed Message Authentication Code (HMAC) example I scrapped together:
https://github.com/zach-king/ArduinoStash/blob/master/src/Spritz_HMAC/Spritz_HMAC.ino

This library supports encryption as well, which is nice, but not needed in my case.

--EDIT--
The SpritzCipher library was actually too slow (about a 50% reduction in network speed) so I must try a different approach. I have found a MD5 library for Arduino which I will try next:
https://github.com/tzikis/ArduinoMD5