Fix wp_term_relationships slow query in get_posts

I have encountered the same issue but with product attributes, since I had more than 20000 products and much more product attributes, the queries were very slow.

What I did was, in order to make it faster, wrote an small plugin converting tags to custom fields and then displayed those on the page, but in your case if you need the tag archive pages and its functionalities, I suppose there is no other way around it.

To avoid max_execution_time try to configure your plugin to execute tag conversion instructions in small chunks,For instance, From posts 1 to 2000 and 2000 to 4000 and so on.

Database indexing might help too.

Finally try to use a cache plugin such as wp_fastest_cache it helps in an immense degree.