Performance issue: Updating list for a simple crowd simulation

I am making a simple flok- or crowd-simulation.

The behaviour is decent for my needs, but the performance is not.

Basicly I have "alot" of objects(soldiers), which need to spread out while moving to a waypoint.

Ive written a simple version of my code here:

---

 List<Soldier> avoidList = new List<Soldier>();

 foreach (Soldier s in gameWorld)
 {
     if (this == s)
          continue;

     if (Distance(s, this) <= 5)
     {
          avoidList.Add(s);
     }
 }

 CalculateNewDirection(avoidList);

---

So basicly, each soldier checks the distance of every other soldier in the scene, and calculates a direction based on the soldiers which are too close.

Like this picture.

Right now im running through x^2 objects.

So if I have 100 objects, i run through 100^2 = 10.000 objects, just to update each individual objects avoidList.

And if i crank it up to 500 objects, i run through 250.000 objects.

Theres gotta be a different and smarter way to do this!

(I've tried using colliders as triggers to add/remove from the avoidList, but that is way slower than this)

Hope someone can enlighten me :)