Você tem que fonte em seu .zshrc:
if [[ -s '/etc/zsh_command_not_found' ]]; then
source '/etc/zsh_command_not_found'
fi
O script é parte do pacote comando não encontrado :
$ apt-cache search zsh_command_not_found
> command-not-found: /etc/zsh_command_not_found