Creating Idividually colorable Provinces on a world map

So I am working on a paradox style grand strategy game with a large World map. The foundation is a 5616x2160 pixels large Texture (currently the one from Victoria II) where all provinces have an individual color. Now a script loops through every pixel and every time it finds a new color, it creates a new Province GameObject which can later store stuff like population, resources, etc... Now I also want these Provinces to be colored according to their respective owner. My current Approach is that every province, once its created, searches the entire pixel array of the texture for pixels of the provinces color and calculates their texture coordinate. then it changes the pixels with the same coordinates on the Texture that is actually visible in the end. The problem here is that the script has to check all ~12.000.000 Pixels ~3000 times for each Province and thus crashing unity and my PC.

This is the Code used on each province:

 void Start(){            
 for(int i = 0; i < pixels.Length; i++)
             {
                 if(pixels[i].r == ProvColor.r && pixels[i].g == ProvColor.g && pixels[i].b == ProvColor.b) 
                 {
                 
                     var width = MainTex.width;
                     Vector2 uv = new Vector2(i % width, i / width);  
                     int y = (int)uv.y;                  
                     int x = (int)uv.x;                 
                     ProvOwnerTex.SetPixel(x, y, color); 
                     ProvPixelPos.Add(uv);     
                 }
             }
             ProvOwnerTex.Apply();
 }

I hope you guys can help me here.