The inbuilt tools do the bulk of the work for you.
Afaik, best practice is to truncate as much as possible and remove any special characters, the inbuilt tool will do the latter you'd need to do the rest yourself.
If you take the title of your product;
Using the tool that'd be
But you'd probably want to remove as much as possible extra information without reducing the actual information, just "hat" would be the purest seo but loses too much description so;
Would the "best" seo result, least as far as I understand it.
You need to rebuild your google search asap, submitting your site map and google shopping links to the new ones should fix that with a day or two, google crawls alot.
Your internal links should dynamically update, as far as cubecart is concerned there is a lookup table against your item id and seo link, unless you've hard coded the links for some reason.