The math might not matter. This thread seems pre-Snowden. Here is a Reuters article dated December 20, 2013:
(Reuters) - As a key part of a campaign to embed encryption software
that it could crack into widely used computer products, the U.S.
National Security Agency arranged a secret $10 million contract with
RSA, one of the most influential firms in the computer security
industry, Reuters has learned.
Documents leaked by former NSA contractor Edward Snowden show that the
NSA created and promulgated a flawed formula for generating random
numbers to create a "back door" in encryption products, the New York
Times reported in September. Reuters later reported that RSA became
the most important distributor of that formula by rolling it into a
software tool called Bsafe that is used to enhance security in
personal computers and many other products.
Undisclosed until now was that RSA received $10 million in a deal that
set the NSA formula as the preferred, or default, method for number
generation in the BSafe software, according to two sources familiar
with the contract. Although that sum might seem paltry, it represented
more than a third of the revenue that the relevant division at RSA had
taken in during the entire previous year, securities filings show.
During this Science Friday podcast Ira asks Matt Green, Martin Hellman (inventor of Public Key Cryptography), and Phil Zimmerman (creator of PGP) what they think the NSA has cracked:
Ira: What are some of the things that we know that the NSA has broken into?
Matt: So we have heard a number of things that we can probably credit for real. … random number generators … we know
that NSA through NIST … has very likely put back doors in some
of those standard algorithms that allow them to essentially break
those systems entirely.
Ira: You mean the NSA created those back doors?
Matt: That's exactly right. So NIST works with NSA --- and they're required to by law. We thought NSA was helping NIST by developing more
secure standards for Americans to use. We now suspect --- and have
strong evidence to believe --- that the situation was exactly the
opposite; that NIST was being used to put out standards that the NSA
Considering these recent revelations the strength of the algorithms seems largely irrelevant. RSA appears to have been a private company somehow bought by the NSA, and DSA was created by NIST itself, which, according to these experts is largely a front for NSA crypto research.
In other words, it really doesn't matter if you are using the random number generators that come with pretty much any modern computer, which OpenSSH and others do.
Pick the one that is the fastest for what you want. In my case, I reuse the same key for a lot of stuff so DSA's faster generation speed is less desirable. Also, maybe there is some wild chance that RSA was actually an independent entity from NIST and NSA, whereas we know DSA was created by NIST.
I personally just use 1028 bit keys because, as we've seen, it really doesn't matter unless someone is placing some requirement on you who still believes bigger keys will protect you. The whole thing is largely just an annoyance to anyone seeking to break in.
ssh-keygenfrom OpenSSH 6.3p1 is 2048 bits. Read the answers below, and you will also find out that 2048 bits is sufficient.