Devi installare postgresql-server-dev-X.Y per creare un'estensione lato server o libpq-dev per creare un'applicazione lato client.
Non è necessario specificare una versione specifica di PG nel Gemfile
Quindi:
sudo apt install ruby-dev libpq-dev build-essential