What are your stats? I simply cannot find a logical way as to how you are not able to kill an Orc or a Brigand after 5 minutes. I personally tested this moments ago.
100 - Str
100 - Dex
25 - Int
While using an NPC bought kryss, an orc took me 31 seconds to defeat and a brigand took me 33 seconds.
For stats, they will gain by using weapon skills however they will gain much faster by using different skills. For example, strength will gain while attacking someone and gaining swords, however, it will gain much faster by using a skill such as herding.