PHP 7.3 может быть недоступно в репо по умолчанию в Ubuntu 16.04, вам нужно добавить стороннее репо. Я часто использовал ondrej repo quiet, и он прекрасно работает.
Запустите следующие команды:
sudo apt-get install software-properties-common
sudo add-apt-repository ppa:ondrej/php
sudo apt-get update
sudo apt-get install php7.3
Для запуска вышеуказанных команд вам понадобится разрешение sudo.