Eu tenho o mesmo problema.
Descobri que o pacote gksudo (gksudo) foi descontinuado . primeiro removido do Debian e depois A Canonical decidiu soltá-lo do Ubuntu 18.04 . Sugere-se que os desenvolvedores de aplicativos usem o PolicyKit (pkexec).
Sugiro olhar para este tópico sobre como usar o comando pkexec em um arquivo .desktop. Eu não tentei ainda (parece um pouco demais para mim e eu não quero estragar tudo).
Isso é o que eu tenho. Talvez alguém tenha uma solução melhor e mais simples.