Все три ключа собираются в первой комнате Вальгаллы (это та в которой предстоит выбрать Путь Оружия) Очередной ключ будет находится на полу справа возле картины на которой изображен Кратос с огромным топором на плече.
Учтите что ключ появляется в этом месте не каждый раз и при очередной попытке пройти Вальгаллу его попросту может там и не быть.
Однако со временем пытаясь снова и снова пройти дополнение вы соберете все три ключа.

Ну и небольшое дополнение - если нет ключа или, даже, он есть - проходить не надо весь цикл - зашли, подобрали/нету и не подобрали - вышли на берег, опять зашли. И так до победного - ключ будет сохраняться.

Ключи начинают появляться после прохождения сюжета Вальгаллы.

Важное дополнение! Новые ключи будут появляться только после того как вы послушаете историю! Взяли ключ прошли пару дверей, послушали покаяние Кратоса, можно идти за новым ключём. Раньше он не появится.