Gitlab prompts for password when using deploy key

I’m just starting with gitlab and I seem to have a problem with the deploy keys. I’m using gitlab CE 8.12.0. I create a key for my deploy user and add the public key as a deploy key in my project. In spite of this all attempts to git fetch from the project prompt me for a password. Clearly something is failing with my key setup.

Below are sample commands on my centos 7 box that I’d like to deploy to I create keys and add the public key as a deploy key.

As user deploy

ssh-keygen -t rsa
\#accept defaults
cat .ssh/id_rsa.pub
\#copy/paste to gitlab deploy key for my project.

\#make an empty repo and try to fetch
mkdir test
cd test
git init .

git fetch https://gitlab.myu.domain/projects/project.git
Username for https://gitlab.myu.domain/projects/project.git

or

git fetch ssh:://gitlab.myu.domain/projects/project.git
deploy@gitlab.myu.domain's password.

Just a shot in the dark. I am also an inexperienced GitLab user.

Check if your repository is Public:
Settings > General > Permissions > Project Visibility: Public)

For some reason, deploy keys work only in public repos for me.