With barbarians, I should say old scandinavian names, and then a title as a surname.
Like Olof Wolvesbane or Ragnar Shieldbreaker