This is a side-effect of Craft's amazing automagical cache system. :) Check out my answer on this question for an explanation of what happens.
Regarding your question of how to fix this, part of the solution is probably what I wrote in the answer, to make sure that you don't create more caches than you need, by caching globally and using the request path as key.
Other ways to counter this problem is to use the ColdCache and CacheFlag plugins. They serve different purposes, and isn't right for all caches, but they have one thing in common, they doesn't save anything to the templatecachecriteria table, which determines the length of the delete stale template caches task. I usually end up with a combination of all three on projects that have a lot of content.
ColdCache is good to use in the cases where you primarily are caching a single entry, and you can get away with breaking the cache when the entry is saved. By using the modified date of the entry as part of your cache key, Craft will create a new cache every time you save the entry (don't worry, the old caches will be deleted when they expire, and doesn't affect performance in any way).
CacheFlag is good to use when you know what sections, globals, categories or... whatever, you're caching. For instance, if you have a news section, and are caching a list of news entries, you could add a flag to the section in CacheFlags settings, wrap the list in the CacheFlag tags and add the flag. Whenever an entry in that section gets saved, all caches with that flag gets deleted and refreshed the next time the list is shown.
Both of these approaches sacrifices something in terms of cache breaking - and it takes some thinking through to get right - but performance wise you gain a lot.
