Использовал BFG Repo-Cleaner на свой страх и риск, это помогло в моем случае.
Если у кого-то проблема, как у меня, рассказываю что делал, т.к. делал не совсем по
инструкции, т.е. без создания "bare repo".
Запустил Repo-Cleaner с необходимыми ключами прямо в папке проекта, после обработки получил пересобранные коммиты с новыми хэшами. Пуш далее я делать не мог, так как первые 4 коммита в локальном репозитории и в удаленном не совпадали. Нужно было либо делать пул и мерджить, либо, как сделал я - отвязал origin в локальном репозитории и привязал новый (предварительно создав на гитхаб). Далее пуш и я получил новый проект на гитхабе со всей историей коммитов.