Here I come. Following from the DSA announcement I've regenerated the ssh/openssl keys for cduce.org.

One the user side:

first ssh to the remote machine and remove the for ~/.ssh/authorized_keys . This will lock you out if you don't remember the passowrd for that machine !

Then, you should remove your ssh keys (from you local machine), and regenerate them with:

At this point you should be able to login back on your remote host using the new ssh key.