Atualização de Tabela

Pessoal, olha o meu problema:
Tenho uma tabela ´Telefones´ com Telefone, Nome, Endereço, Bairro, Cidade e UF mas quero criar uma tabela só pra Cidade e UF pra economizar espaço. Criei essa tabela (´TblCidade´ ) com a seguinte estrutra: idCidadeUF int, Cidade Varchar(30), UF Varchar(2) e adicionei à tabela ´Telefones´ o seguinte campo: FkCidade int.
A tabela ´Telefones´ tem mais de 20 milhões de registros e preciso dar um ´While´ na mesma fazendo a seguinte verificação:

Declare @ID = int
if not Exists (Select TblCidade.* from TblCidade, Telefone where TblCidade.cidade= Telefone.cidade and TblCidade.UF = Telefone.UF)
begin

set @ID = @ID +1
insert TblCidade Values (@ID,Telefone.cidade,TblCidade.UF)
e aqui tenho que atualizar o campo FkCidade da tabela ´Telefones´ com a variável @ID


end


Depois disse pronto, vou excluir da tabela ´telefones´ os
campos ´cidade´ e ´UF´.
Alguem poderia me indicar uma forma de fazer isso que descrevi acima?
Fico grato desde já!