Which ssh keys are these? When you first generate all keys when first using sshd, it takes a lot longer, so I assume you mean a different kind of ssh keys.
ssh-keygen -t dsa takes:
about 492 CPU seconds on a 50 MHz m68040
about 106 CPU seconds on a 66 MHz m68060
Yes, it'd take AGES on an LC III m68030. On the other hand, -m68030, -m68040, and -m68060 options help a lot with things like ssh.