Você precisa remover %{ e %} da parte do PROMPT que imprime o diretório de trabalho.
PROMPT='%(?..%F{red}%?%f:)%F{blue}%n%f:%F{green}${PWD/#$HOME/~} %(!.%F{red}.%f)%# %f'
As sequências %{ e %} devem ser colocadas em torno de bits do prompt que não afetam a posição do cursor (por exemplo, uma seqüência de controle codificada). Por cercar algo que realmente move o cursor (imprimindo seu diretório de trabalho atual), você está confundindo a noção de zsh de onde o cursor está; quando precisar redesenhar parte da linha atual (por exemplo, quando você usa o C-r para pesquisar), ele acaba colocando o cursor no local errado.
Você pode verificar isso alterando para um diretório com uma representação impressa maior: se você for cd /tmp , o cursor ficará fora de lugar por 4 colunas (o comprimento de /tmp ) em vez de 1 (o comprimento de ~ ).
Além disso, você geralmente pode usar %~ em vez de ${PWD/#$HOME/~} para incluir o diretório de trabalho atual. Assim, se essa foi sua única substituição, você poderá desativar o PROMPT_SUBST.