Create an ECDSA SSH key pair (ssh-keygen -t ecdsa) for the user that runs jenkins.
Put the public key (~/.ssh/id_ecdsa.pub) into into the appropriate authorized_keys file on a build slave.
You are now able to connect to the build slave by using public key authentication with the ECDSA key.

Now run Jenkins under that account. Make sure that you update the SSH credentials plugin to 1.8. Configure the build slave. Choose "From the Jenkins master ~/.ssh" as your credentials to use the ECDSA key.

When Jenkins tries to connect to the build slave, it fails with the exception "Caused by: java.io.IOException: Invalid PEM structure, '-----BEGIN...' missing"

This exception comes from the trilead-ssh2 library https://github.com/jenkinsci/trilead-ssh2/blob/master/src/com/trilead/ssh2/crypto/PEMDecoder.java which has no ECDSA support built in yet.

Interestingly, version 1.8 of the SSH credentials plugin was released just for the support of ECDSA keys.

Looking at the changes for 1.8 https://github.com/jenkinsci/ssh-credentials-plugin/commit/93e61a2cb9da782bdfefd8ce1375c1b2fd592cc0 that nothing but the list enumeration with the key types and the version were changed.

Possible workarounds are downgrading to 1.7.1 or deleting the ECDSA keys.

Please revert the changes made in version 1.8 until trilead-ssh2 supports ECDSA keys.