C# Fastest way to replace bunch of colors in high quality Image?

Question

I have some 4k images (.png, 3840p*2160p) in which I want to replace around 2500 colors each.

I have an Color[] Array of the 2500 current Colors and one with 2500 new Colors that are always different.

Currently I have an System.Drawing.Imaging.ColorMap Array in which I push 2500 single ColorMap objects with their respective OldColor & NewColor properties set to each value from my other arrays.

Then I can do the following:

[...]
ImageAttributes imageAttributes = new ImageAttributes();
imageAttributes.SetRemapTable(colorMapArray);
Rectangle rectangle = new Rectangle(0, 0, myImage.Width, myImage.Height);
Graphics graphics = Graphics.FromImage(myImage);
graphics.DrawImage(myImage, rectangle, 0, 0, myImage.Width, myImage.Height, GraphicsUnit.Pixel, imageAttributes);
myImage.Save("myImageWithReplacedColors.png");

This technically works and replaces all of my colors with their new values but its very very slow. (takes up to multiple seconds)

What options do I have to speed up this process? ..Or other ways to get the same result? I've been looking for a few days but haven't really found anything

If that helps, the 4k image and the Array with the Current Colors that should be replaced are always the same. So I could save them special, for example as a byte array(?)