Quine was very pragmatic about the issue.
These examples come from a book by Prof. Gibson, Quine scholar.
J.S. Mill said mathematics was empirical.
A.J. Ayer, who was an empiricist, says the necessity of logic and mathematics is real, and necessary because analytic, but does not provide truth about the world.
Quine rejects both of these men, supposedly: "The justification of logic and mathematics is on a par with the justification of theoretical physics. Logic, mathematics, physics are needed in the construction of our overall best theory of the world, and all three are justified to the extent that they make that theory come out right, .ie maximize true predictions." Prof. Roger Gibson Jr. on Quine.
Huh? Circular somehow?
Now to be fair to Quine, his philosophy fits within a system. A pragmatic system. He sweated over this pretty hard. (Edit: like I'm doing) It hangs together as a system, and it would require me to set out his entire pragmatic system to make Quine's statement above make sense.
EDIT. After reading what Not-here wrote above, I think Gibson might have skipped over a point. It seems that Quine accepted Ayer-like position (analytic) essentially, but Ayer (and Ayer is not the only one) said such mathematical reasoning does not provide truth about the the world, therefore the use of math and logic and theoretical physics would need a justification if used to advance our overall theory of the world, and all three are justified to the extent they make our theory of the world come out right, that is to say, that they maximize true predictions.
(The paragraph above is still not right because it does not state what not-here was referring to, and the question appears to have already been answered, which is a good thing because I am certainly not making any progress with Quine's thought.)
Einstein's position and the position of Ayer seem to be closer to what mainstream philosophy has to say today. But I'm not up to date on it. Quine's position is subtle and pragmatic, but will not satisfy the mathematicians. None of the three philosophers mentioned is probably able to satisfy a mathematician.
All of this is apt to drive the mathematicians insane. This lack of clarity and the looseness of it is because we are still confused about just exactly what mathematics is. We may never figure it out.
Do what the mathematicians do and forget about it. Keep doing mathematics.
Sure you can do proofs. Just follow the rules of the game. Deduction. These truths were never true in the real sense of the world (see Ayer). However, oddly, strangely sometimes when math touches the world it seems to be a match made in heaven! When this happens, mine it for all it's worth.
See SEP on Quine as not-here suggests. You can also read about philosophy of math in MacMillan Encl Phil. 10 vols