Setting up deploy keys is not something one does very often, and accordingly when one comes to do it, it’s something that needs to be looked up from piecemeal locations on the internet! Thus, as an aide memoire for me and anyone who wants it, here is what I do.

1. Create a key pair. I don’t put these in my local .ssh folder, since they won’t be used by the SSH system on my development machine at all. So, to start with, I do ssh-keygen -t rsa -b 4096 -C "hello@jondh.me.uk". When it prompts me for a filename, I use a file in the same directory, e.g. agnes_deploy. The answer to the passphrase (twice) should be just Enter (i.e. no passphrase).
2. Deploy the key remotely, by running ssh-copy-id -i agnes_deploy root@agnes.jondh.me.uk, specifying the name of the (private) key specified in item (1). If you do not have passwordless SSH set up to this machine, it will prompt for the password (I tend to have this already set up, so it should go through without further prompting). The console output is given below.
3. In the CircleCI interface, go to the “SSH Permissions” screen from the cog/configuration icon in your project. The URL will be of the form “https://circleci.com/bb/user-name/project-name/edit#ssh”, with of course suitable swaps for your specific user and project name. You do not want the “Checkout SSH Keys” screen, that’s for fetching your code from a Git host.
4. Add/integrate the YAML configuration below to test an arbitrary command on your server. If this test command succeeds, then you are ready to modify this to run commands remotely.

From here, you can do what you like: Git clones, Docker logins/pulls/restarts, etc.

Here is the console output from the remote key deployment:

ssh-copy-id -i agnes_deploy root@agnes.jondh.me.uk
/usr/bin/ssh-copy-id: INFO: Source of key(s) to be installed: "agnes_deploy.pub"
/usr/bin/ssh-copy-id: INFO: attempting to log in with the new key(s), to filter out
  any that are already installed
/usr/bin/ssh-copy-id: INFO: 1 key(s) remain to be installed -- if you are prompted now
  it is to install the new keys

Number of key(s) added: 1

Now try logging into the machine, with:   "ssh 'root@agnes.jondh.me.uk'"
and check to make sure that only the key(s) you wanted were added.

And here is the YAML config:

version: 2
jobs:
  deploy:
    working_directory: /app
    docker:
      - image: docker:17.05.0-ce-git
    steps:
      # Adds the keys from the UI so we can access a remote service
      - add_ssh_keys
      # This gets the local Docker service started
      - setup_remote_docker
      - run:
          name: Add SSH key to known hosts, try a test command
          command: |
            ssh-keyscan -H agnes.jondh.me.uk >> /root/.ssh/known_hosts
            ssh root@agnes.jondh.me.uk ls /