No observo este comportamiento aquí. Uso ssh-agent del paquete openssh-client de Ubuntu 12.04, es decir, "OpenSSH_5.9p1 Debian-5ubuntu1, OpenSSL 1.0.1 14 de marzo de 2012". Modifiqué la secuencia de comandos de Python para seleccionar mi clave DSA en lugar de mi clave RSA (¿hiciste lo mismo?) Y recibo, como se esperaba, firmas aleatorias (no es necesario reiniciar ssh-agent , dos firmas sucesivas son distintas).
Es teórico teóricamente posible hacer firmas DSA deterministas a través de un proceso conocido como desaseatorización , lo que básicamente significa que el valor aleatorio k es no ya se generó de manera aleatoria, pero con un PRNG sembrado con el mensaje que se firmará (o su hash) y una clave secreta (que puede ser la propia clave privada DSA, o una clave simétrica almacenada a lo largo de la clave privada DSA, si hay espacio para esa clave adicional). Hay que tener en cuenta algunas sutilezas, porque el valor k debe seleccionarse con una aleatoriedad uniforme impredecible. Hay un borrador de RFC sobre ese tema, pero aún es bastante nuevo: escribí la primera versión en marzo de 2011. No tengo conocimiento de ningún otro esfuerzo de estandarización en la aleatorización de DSA o ECDSA. Por lo general, cuando un sistema de firma DSA parece ser determinista, es debido a un error muy grave en el generador de números aleatorios (como ocurrió a Sony para las firmas ECDSA utilizadas en el software de PS3).
¿Está seguro de que realmente está utilizando una clave DSA? Una firma DSA tiene una longitud de 40 bytes en SSH (dos enteros de 160 bits, ya que SHA-1 se utiliza como función hash), mientras que una firma RSA será más grande (128 bytes para una clave RSA de 1024 bits).