Site Health is a tool put together by people who know nothing about the specific details of your hosting. It should only be used as a very general guide. Now to your issue.
There was a new release of the PHP imagick
extension a couple months ago, the first new release in more than two years. The good news is that it’s the first version of the extension to fully support PHP 7.3. The bad news is that it doesn’t work correctly unless ImageMagick 7 is installed on the server. So here are the two scenarios:
PHP 7.3 and IM7 — use imagick 3.4.4
PHP 7.3 and IM6 — your host is correct, and Site Health was wrong
Many hosts do not offer the imagick extension in shared hosting plans because it’s a CPU pig, worse in fact than the GD extension. Other hosts will not install ImageMagick 7 due to its memory footprint and/or its compatibility issues with IM6 scripts. One hopes neither of these was the case with you, since it’s a bad sign when a host lies to a client or is incompetent.