find . -type f -or -type l | sort | xargs --delimiter=\\n md5sum -b
This didn't take all THAT long on RHEL 6.4, 5.5, Ubuntu Server 12.04 or my Mac. I ran on all 4 as root. All of our machines except my Mac are pretty close to default except they are pretty locked down on the Firewall side.