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.