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

Шифрование нужно использовать, если вы хотите скрыть приватные данные от посторонних глаз.

На девелоперской машине нужно установить travis gem. gem install travis ставится долго, создаётся впечатление, что ничего не происходит, но нужно просто немного подождать.

sudo apt-get install rubygems
sudo gem install travis
travis encrypt "__PSW__=password"

Чтобы автоматически добавить шифрованную строку в конфигурационный файл travis .travis.yml, нужно команду encrypt выполнить с ключом --add

travis encrypt "__PSW__=password" --add