Convert url string to pretty url...

I currently have a WordPress site where I'm passing url variables:

mysite.com/my-page/?id=123&id2=456

I would like to clean up the url string so that the string shown above would appear as:

mysite.com/john-does-profile/

Is there a plugin that can accomplish this? Would it be better to go via the .htaccess RewriteRule route?

Any direction is greatly appreciated