Deploy ключи на travis используются только при клонировании основного репозитория. Чтобы склонировать зависимые приватные репозитории, можно использовать https схему c указанием пользователя и пароля вместо git@github.com, deploy ключи, пользовательские ключи или Api token. 

Если это не настроено, то во время билда в travis при клонировании приватных подмодулей будет возникать ошибка:

ERROR: Repository not found.
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.

Ниже рассмотрим 2 из возможных вариантов что нужно сделать, чтобы в travis работало клонирование приватных подмодулей.

1. Использовать https схему c указанием пользователя и пароля вместо git@github.com.
2. Сгенерировать пользовательские ключи

1. travis клонирование через https схему

Для этого, во-первых, отключим инициализацию подмодулей:

git:
  - submodules: false

Во-вторых, выполним операцию замены git-адресов репозиториев в файле .gitmodules на использование https схемы с указанием имени пользователя и пароля:

before_install:
  - sed -i "s/git@github.com:/https:\/\/__LOGIN__:__PSW__@github.com\//" .gitmodules
  - git submodule update --init --recursive

Имеет смысл создать нового пользователя с правом только на pull (без push). И тогда вместо __LOGIN__ и __PSW__ нужно подставить его логин и пароль. Если использовать свои логин и пароль, то пароль увидят все члены команды, имеющие доступ к репозиторию. Впрочем, пароль можно скрыть. Travis предоставляет возможность шифрования данных. Как в travis создать шифрованную переменную и использовать её во время билда читать тут. 

.travis.yml файл одного из проектов:

# see http://about.travis-ci.org/docs/user/languages/php/ for more hints
language: php

# list any PHP version you want to test against
php:
  # aliased to a recent 5.4.x version
  - 5.4
env:
  matrix:
    secure: "Vjxaw2ZaOPS50gB2sNtol4gdCydHDLP2wFIzDZrzQ7PO9o3vwXDFjpspXTGUm5FVdUaRLZdPdHZq097oJ8cghrCOnK2ms9qt32Eo70rHdKynSTSQraH2RRD9cXsFRzhMNINGdV9K6zLulUX2G/nWoPW59dniwgfoWL9SzWEbsmw="

services:
  - rabbitmq
  - memcached

# disable the default submodule logic
git:
  submodules: false

# Use sed to replace the SSH URL with the public URL, then initialize submodules
before_install:
  - sed -i "s/git@github.com:/https:\/\/bopoda:$__PSW__@github.com\//" .gitmodules
  - git submodule update --init --recursive

# execute any number of scripts before the test run, custom env's are available as variables
before_script:
  - sudo apt-get update

  - curl -sS https://getcomposer.org/installer | php
  - sudo mv composer.phar /usr/local/bin/composer
  - cp travis.composer.json composer.json
  - sudo composer update

  - mkdir -p 3rdparty/PHPUnit/Util
  - mkdir -p 3rdparty/PHPUnit/Extensions/Database/DataSet
  - cp vendor/phpunit/phpunit/src/Util/Filter.php 3rdparty/PHPUnit/Util/Filter.php
  - cp -pr vendor/phpunit/dbunit/PHPUnit/Extensions/Database/DataSet/* 3rdparty/PHPUnit/Extensions/Database/DataSet

  - sed -i "s/short_open_tag = .*/short_open_tag = On/" ~/.phpenv/versions/$(phpenv version-name)/etc/php.ini

  - printf "\n" | pecl install imagick
  - sudo apt-get install whois
  - sudo apt-get install dnsutils
  - sudo ./bin/provision/cld2
  - sudo ./bin/provision/db

  - echo "extension = memcached.so" >> ~/.phpenv/versions/$(phpenv version-name)/etc/php.ini
  - echo "extension = amqp.so" >> ~/.phpenv/versions/$(phpenv version-name)/etc/php.ini
script:
  - phpunit --bootstrap=tests/bootstrap.php tests/

2. Клонирование приватных подмодулей travis с помощью пользовательских ключей

Описанный выше вариант с клонирванием через https схему, конечно, работает, но он своего рода костыль. Рекомендуется следующий ход действий.

Суть в том, что deploy keys дают доступ только к единственному репозиторию. Github не позволяет снова задействовать ключи. Я думаю, это сделано на github в целях безопасности.

Ключи пользователей (User Key) могут иметь доступ ко множеству github репозиториев. Поэтому, оптимальным будет вариант иметь пользователя с правом только на pull (не push), для которого нужно будет сгенерировать ssh-ключи. Далее при билде сабмодули будут клонироваться от этого пользователя. На самом travis используется точно такой же способ - юзер travisbot с правами только pull. Для генерации пользовательских github и travis ключей воспользуемся travis gem командой travis sshkey --generate -r ORGANIZATION/REPO.

Собственно, это всё что нужно. Успешно выполнив эту команду travis sshkey --generate, всё начнёт клонироваться. Только сразу нужно установить rubygems и сам travis.

sudo apt-get install rubygems
sudo gem install travis

travis sshkey --generate -r vicman-wi/wi-backend
Username: user_name
Password for user_name: ****************

Store private key? |no| -- no

Generating RSA key.
Uploading public key to GitHub.
Uploading private key to Travis CI.

Your Ruby version is outdated, please consider upgrading, as we will drop support for 1.8.7 soon!
not logged in, please run travis login --pro

Введите команду travis login --pro и авторизуйтесь github пользователем. Затем повторите команду генерации ключа travis sshkey --generate -r ORGANIZATION/REPO