I compiled 2.6.28.10 from vanilla kernel source. I made one change to the .config, which was to select R5000 as CPU type, instead of the default "R4x00". Now the the DSA2 host_key is generated and openssh-server installs fine. So looks like a bug in the Lenny MIPS kernel or a problem with running an R4x00 kernel on a R5000. Anyway, hope this might help someone else.