For a protocol where the server presents its signature to prove authenticity (e.g. IKE/SIGMA/STS with only one party authenticated), it's essential that the signing is extremely cheap, while verification can be almost arbitrarily expensive.
RSA appears to be the worst alternative, but what about DSA vs. ECDSA? Is there some other signing algorithm that could be even better (i.e. consume even less CPU to calculate)?