That’s strange, because PHP 7.1 is still supported by Nextcloud 16.0.3.
Nevertheless, there are always to different PHP components installed and used on a server, the PHP CLI version and the WEB version. Are you sure, that both components have been upgraded to v7.3?
I had inadverently downloaded a very old version - I grabbed latest-9… from https://download.nextcloud.com/server/releases/ without realizing they were sorted by version number and the most recent was at the bottom. I’m reinstalling version 16 and things seem to be going fine.