Du kommer inte att tappa placeringarna.
Google är snäll mot förändringar och gillar förändringar om det är bra förändringar.
Tycker absolut att du ska dumpa frames.

Självklart skall du skippa frames, finns det något tillfälle då frames faktiskt är att föredra? Sidan brukar oftast få en mycket bättre helhet om man skippar dem. För SEO samt användbarhet är frames absolut ingen höjdare.

På vilket sätt skulle det vara den bästa lösningen?

Frames är i sej inte negativt ur SEO-synpunkt, det är hur man använder frames som ofta är negativt. Om man ser till att man har en bra intern länkstruktur så funkar frames bra. Men om man ändå funerar på att bygga om en site så är det absolut dags att skippa frames. Då slipper man ta med det i beräkningen när man lägger upp enn SEO-strategi.