Debe instalar postgresql-server-dev-X.Y para crear una extensión del lado del servidor o libpq-dev para crear una aplicación del lado del cliente.
No necesita especificar una versión específica de PG en su Gemfile
Entonces:
sudo apt install ruby-dev libpq-dev build-essential