You are right that the message is confusing and has therefore been changed in the new versions released a few hour ago.
The recommended version was hardcoded in our software at the time the version was finalised (NOT when it was released). The version you are using was finalised in early December, a few days before PHP 7.3 became End of Life. It was released a month later because we do not make releases during the holiday season.
The trigger for the old PHP version message is your server date and its comparison with the published lifecycle dates of different PHP versions, as published on php.net at the time the version of our software was finalised. Since you are running the software after PHP 7.3 entered its Security Only Fixes phase of its life you see this message.
This of course presents a problem. We cannot go back in time and retroactively change the recommended PHP version. Moreover, we will inevitably reach a point where PHP 7.3 will become end of life and the hardcoded recommended version in our software would still be 7.3. Therefore the recommended version, while a good idea 2-3 years ago when people didn't know they could upgrade to PHP 7, is no longer fit for the purpose and has been removed in all versions of our software published today (February 5th, 2021).
From now on you will only receive a message telling you that the PHP version you are using is old or End of Life and you will be directed to our Compatibility page to find which versions of our software will run on your Joomla and PHP versions, in hope that seeing newer PHP versions will help you understand that you can upgrade to one of them.
In your case, you should upgrade to PHP 7.4 for now. PHP 8.0 is still a bit too new and many developers don't support it yet (we do support it but Joomla 3.9 itself still has a few minor issues with it you will only see if you set Error Reporting to maximum). If you ask me again around June I will try likely tell you to upgrade to PHP 8.0 because it will be supported by all extensions in active development. All of that if you were always asking me about the same version of our software. That is to say, the PHP version I'd recommend is not something static, it's something dynamic that has to do with the PHP support lifecycle, Joomla's support of newer PHP versions and third party extensions' support of newer PHP versions.
If you are wondering what is our policy for supporting PHP versions please refer to the text at the top of https://www.akeeba.com/compatibility.html
Nicholas K. Dionysopoulos
Lead Developer and Director
🇬🇷Greek: native 🇬🇧English: excellent 🇫🇷French: basic • 🕐 My time zone is Europe / Athens
Please keep in mind my timezone and cultural differences when reading my replies. Thank you!