DSA, RSA, ECDSA etc - which one is cheapest for signing? 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)?
From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.)

Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant implementation) since it does not require an inversion modulo the curve order. And as mentioned, there is also Ed25519, which uses a special, non-standard curve in order to be more efficient.