Capistrano asks for password when deploying, despite SSH keys

My ssh keys are definitely set up correctly, as I'm never prompted for the password when using ssh. But capistrano still asks for a password when deploying with cap deploy. It doesn't ask for the password when I setup with cap deploy:setup though, strangely enough. It would make the deployment cycle so much smoother without a password prompt.

Specifics: I'm deploying a Sinatra app to a Dreamhost shared account (which uses Passenger). I had followed a tutorial for doing so long back, which worked perfectly back then. Something broke since. I'm using capistrano (2.5.9) and git version 1.6.1.1. Here's my Capfile:

load 'deploy' if respond_to?(:namespace) # cap2 differentiator

set :user, 'ehsanul'
set :domain, 'jellly.com'

default_run_options[:pty] = true

# the rest should be good
set :repository,  "ehsanul@jellly.com:git/jellly.git"
set :deploy_to, "/home/ehsanul/jellly.com"
set :deploy_via, :remote_cache
set :scm, 'git'
set :branch, 'deploy'
set :git_shallow_clone, 1
set :scm_verbose, true
set :use_sudo, false

server domain, :app, :web

namespace :deploy do
  task :migrate do
    run "cd #{current_path}; /usr/bin/rake migrate environment=production"
  end
  task :restart do
    run "touch #{current_path}/tmp/restart.txt"
  end
end

after "deploy", "deploy:migrate"

And here's the output of what happens when I cap deploy, upto the password prompt:

$ cap deploy
  * executing `deploy'
  * executing `deploy:update'
 ** transaction: start
  * executing `deploy:update_code'
    updating the cached checkout on all servers
    executing locally: "git ls-remote ehsanul@jellly.com:git/jellly.git deploy"
/usr/local/bin/git
  * executing "if [ -d /home/ehsanul/jellly.com/shared/cached-copy ]; then cd /home/ehsanul/jellly.com/shared/cached-copy && git fetch  origin && git reset  --hard ea744c77b0b939d5355ba2dc50ef1ec85f918d66 && git clean  -d -x -f; else git clone  --depth 1 ehsanul@jellly.com:git/jellly.git /home/ehsanul/jellly.com/shared/cached-copy && cd /home/ehsanul/jellly.com/shared/cached-copy && git checkout  -b deploy ea744c77b0b939d5355ba2dc50ef1ec85f918d66; fi"
    servers: ["jellly.com"]
    [jellly.com] executing command
 ** [jellly.com :: out] ehsanul@jellly.com's password:
Password:
 ** [jellly.com :: out]
 ** [jellly.com :: out] remote: Counting objects: 7, done.
remote: Compressing objects: 100% (4/4), done.

What could be broken?