Je moet postgresql-server-dev-X.Y installeren voor het bouwen van een server-side extensie of libpq-dev voor het bouwen van een client-side applicatie.
Je hoeft geen specifieke versie van PG op te geven in je Gemfile
Dus:
sudo apt install ruby-dev libpq-dev build-essential