You could do search+replace throughout with the database or manually, and a bunch of 301 redirects.. You’re adding-to, and a hyphen isn’t a standard break in wordpress (like the slashes are), so it can get cumbersome.
I would consider using .htaccess rewrite
to help: I’d configure the new permalink to:
/%category%/%postname%/%post_id%/
then, with .HTACCESS do a rewrite that would “change” your permalink structure to what you’d really like it to be..
You’ll have to look it up on how to rewrite it properly – I’m guessing here, but basically you’re identifying the URL with your custom permalink (with the hyphen), but telling the server it’s actually a backslash (as WordPress expects). so the world see’s the hyphen, but the code sees the backslash:
RewriteEngine On
...
/(.+?)/(.+?)/(.+?)/ /$1/$2-$3/
...
I suggest this because: WordPress should be able to redirect old /%category%/%postname%/
to the new /%category%/%postname%/%post_id%/
automatically, with no problem, so old links are preserved, and the URL after the redirect can be altered with rewrites to change the backslash to the hyphen to the public.