In my current setup, the clients are bundled with the server's public key. The client encrypts a nonce and sends it to the server which uses its own nonce and the nonce received from the client to set up a symmetric encryption key and sends back the unencrypted nonce + an encrypted response.
Unfortunately, this makes the server wide open to both deliberate and accidental DOS attacks.
As an example of the latter, let's say a server is taken down and the clients all try to reconnect. That will means 100-1000 (non-malicious) connects/s from different ips.
What are my options aside from reducing RSA key size?
Edit
What about any of these strategies:
Move the authentication to a separate server, which securely hands out encryption keys with an expiry date. When logging in to a server, the client presents an identifier that the server can use to retrieve the encryption key to use.
Put RSA decryption in an unbounded queue with sufficiently low thread priority. When a client logs in, it will either automatically get logged in (if there are sufficient resources), or put in a login queue. Until the decryption is scheduled, the client will get updated information about how close they are to get their login completed.
Put RSA decryption in a bounded queued queue with sufficiently low thread priority. If the queue is full, then the connection is refused with a message that the login queue limit is reached and the client can retry later.