It's important to keep in mind that DSS-style signatures are twice the hash
size. This is one of their nicest features; they do not grow with the
modulus. A signature of a 3072/256 key will be 512 bits (plus overhead).
As for generating long modulae, it's not that big a problem, altough it has
to be noted that generating a modulus for DSA takes more than just
generating a prime that big; DSA moduli p are such that p-1 is divisible by
some large (hash-sized) q. The generation of such moduli takes substantially
longer than generating primes. For 3072/256 on a 500MHz intel, it would take
approx. three minutes, provided that the random stream is available without
waiting.
On the other hand, the overwhelming majority of DSS implementations use
pre-calculated moduli, as there are no security hazards associated with
using a common modulus for DSS. When keys need to be generated frequently,
a pre-calculated modulus is the way to go. If one just needs to generate a
personal signature key for the next five years, one can wait three minutes,
in case they want to show off a self-generated modulus.
--
Daniel