They are both correct but they have slightly different emphasis.
"Who is John with?" emphasises John as the main protagonist and we wonder how John could be with someone like that.
"Who is with John?" emphasises the other person - the focus is more on them than on John