This has very little to do with the modern issue of action at a distance vis a vis entanglement, and everything to do with the prevailing belief in an aether during Newton’s time. Einstein meanwhile, was actually commenting on entanglement physics.
Newton wrote, "It is inconceivable that inanimate Matter should, without the Mediation of something else, which is not material, operate upon, and affect other matter without mutual Contact."
Einstein wrote, "I cannot seriously believe in it because the theory cannot be reconciled with the idea that physics should represent a reality in time and space, free from spooky actions at a distance."
Newton was talking about gravity, Einstein about entanglement. But the objection is essentially the same one. That's the reason that Newton's quote above is included in an article on the principle of locality.