Dovresti:

1) Cambiare le url (con il trattino)
2) Fare dei redirect 301 (Permanent) lato server con il file .htaccess pagina per pagina
3) Controllare tutti i redirect manualmente
4) fare la nuova sitemap e postarla a google

Se fai le cose fatte bene dovresti migliorare (non credo che google penalizzi per una grande mole di redirect - però voglio informarmi a riguardo).

Fatto questo pian piano google indicizza le nuove pagine (con le nuove url) e cancella quelle vecchie dal database.
Tu però non toccare le vecchie pagine finchè sono presenti negli indici di google.