É um pouco exagerado, mas funciona aqui:
$ rename 's/^Karaoke (.+) - (.+) - \w{11}\.mp4$/ - .mp4/' * -vn
Karaoke banana - cher - 12345678901.mp4 renamed as cher - banana.mp4
Você precisará desativar -n
do final para renomear os arquivos. Eu deixei a segurança.
O que estamos fazendo aqui é encontrar qualquer arquivo que corresponda a esse padrão, capturando o artista e a trilha dentro desse padrão e então substituindo a coisa toda por esses dois grupos (e alguma formatação e extensão).
Eu não posso prever o que aconteceria se você tivesse artistas com -
em seus nomes. Provavelmente nada de bom, mas traços simples (sem os espaços) devem ficar bem.