There isn’t any real way to do this in bulk with 20k posts.
The biggest issue is the number of posts.
You could possibly build an action, I don’t have exact code.
add_action('init', 'my_modify_slugs');
function my_modify_slugs() {
// query posts
// limit posts to 100
// use the "paged" arg of WP_Query
// loop over posts and alter each post
}
Basically you load the page, the action gets 100 posts and alters them. Then you update the “paged” argument to get the next page of posts. You step through the posts 100 at a time. You might be able to get away with doing more than 100 at a time. You could increase this number and test until your site times out and then lower it to a number that can be done before timeout. Then step through pages.
