First off, don’t drop them into boiling water. The way to boil potatoes is to start them in cold water and bring to a boil. Why? Because, as you pointed out, they take a while to cook, and if you drop them in boiling water, the outside bits will cook before the inside of the potato is done.
Starting them in cold water allows them to slowly heat up and cook all the way through.
Most red potatoes will be done in 15-25 minutes. It all depends on size - I try to buy the smaller ones, between 1" and 3" in diameter. If your potatoes are larger, they’ll take longer. If you have a mix of sizes, cut the larger ones in half (or quarters) so all the potatoes are roughly the same size, otherwise the big ones will be hard when the small ones are done.