I assume that your problem is that these variables are only set in terminals but not in programs started from GNOME/KDE/... (where .bashrc and the like are not sourced).
Hence, tramp will not know anything about the ssh-agent and prompt you for the password. In that case you should try to find a way to make your ssh-agent known to the session.
For example, I am using KDE, and there is a script in /etc/kde/env/ with the following content:
$ cat /etc/kde/env/agent-startup.sh
# Agents startup file
#
# This file is sourced at kde startup, so that
# the environment variables set here are available
# throughout the session.
# Uncomment the following lines to start gpg-agent
# and/or ssh-agent at kde startup.
# If you do so, do not forget to uncomment the respective
# lines in KDEDIR/shutdown/agent-shutdown.sh to
# properly kill the agents when the session ends.
if [ -x /usr/bin/gpg-agent ] && [ -z "${GPG_AGENT_INFO}" ]; then
eval "$(/usr/bin/gpg-agent --daemon --pinentry-program /usr/bin/pinentry-qt4)"
fi
#
if [ -x /usr/bin/ssh-agent ] && [ -z "${SSH_AGENT_PID}" ]; then
eval "$(/usr/bin/ssh-agent -s)"
fi
and a similar script to shut the agents down.