First, potato is not the same as potato. Conventionally, potato salad is always made with waxy potatoes, because mealy potatoes' outer layers disintegrate when tossed with the sauce, much like making risotto. They are also less creamy in texture. But there is also the school of using mealy potatoes, because they absorb more seasoning, and also because some people like the soft texture. If you decide to go with mealy, use an acid in the cooking water (depending on your seasoning, choose vinegar, citric acid, or the neutral tasting cream of tartar). This will firm the potatoes. It isn't necessary for waxy potatoes.
Second, the cooking time depends strongly on size. You must cut them very evenly. Else you will have both undercooked and overcooked potatoes in the pot at any given moment (up to the time when you only have overcooked ones). Smaller pieces are easier to work with.
Third, you want to heat them as gently as possible. Start them in cold water, and cook them at a simmer, not at a boil.
There is no way to predict when the potatoes will be ready. Even if you cut them to the same size every time, the sort and the age of the potatoes will result in varying cooking times. When the time is near, you must look after them and try them constantly. Take out a piece, cut it in half, cool it in cold water, and chomp on the exact center. If it isn't crunchy, stop the cooking immediately and remove the water. The time window in which they are just right is quite short. Season them while they are hot, they will then absorb the sauce instead of just swimming in it the way cold potatoes do.