How to tell when an Entropy Key is overloaded?

The only two things that come to mind is trying to measure the response time of your entropy server (there should be a significant increase in latency if it can't keep up) or pooling /proc/sys/kernel/random/entropy_avail and monitoring how much entropy you have (I'm assuming that egd is using /dev/random and not the hardware directly).

It looks like the source tarball for ekeyd has a munin plugin for providing ekey statistics.

Even if you're not running munin I guess it would be possible to extrapolate the script into something usable for your infrastructure.

I think we both know the authors of the device and software though, so might be worth prodding them. :-)