Você precisa instalar postgresql-server-dev-X.Y para construir uma extensão do lado do servidor ou libpq-dev para construir uma aplicação do lado do cliente.
Você não precisa especificar uma versão específica do PG em seu Gemfile
Então:
sudo apt install ruby-dev libpq-dev build-essential
