Long 'Deleting stale template caches'
The {% cache %}, by default will cache it's contents on a per URL and per locale basis.

A lot of times when we see the behavior you're seeing, that's not the desired behavior and you should be using the {% cache globally %} parameter, where Craft stores the cached segment only on a per locale basis and drastically reduces the number of rows in the database table.

I'd inspect everywhere you're using the tag and if it makes sense to use globally parameter, swap to that.

You can then clear the contents of your template cache tables (under Settings->Tools->Clear Caches Tool) and the database tables shouldn't grow anywhere near as large, letting the delete stale template caches task run faster.