Changing permalink structure

Hey!

I’m running a magazine website with the following permalink structure
/%category%/%postname%/

There are approximately 500 posts having this permalink structure on my site. However due to various reasons, I’d like to change this structure to the following structure
/%post_id%/%postname%/

Before doing that, I would like to know how such change will affect my site, its navigation, its ranking on google, bing, etc. There are some forum discussion on this matter, but I couldn’t come across any unique answer.

Besides that, what would be the most appropriate way to update the permalink structure? Shall I use default wordpress controls to accomplish that or shall I use a plugin to handle that?

Thanks.