The Fury Out of Time, by Lloyd Biggle Jr. First published in 1965, so you easily could have read it the following year. I first read it as a library book in the 1980s. As it happens, I purchased a copy a few years ago so I could refresh my memory of it. (As a kid, I had enjoyed all of Biggle's science fiction novels that I could find.)
Here are some plot points which correspond with the details you remembered.
The protagonist is Major Bowden Karvel, known as an intelligent and dedicated military pilot who was considered to have a very bright future ahead of him in the U.S. Air Force -- until he somehow lost one leg, and was forced to leave the service because of medical disability. As we first meet him, he hasn't gotten over the disappointment of having his military career cut short. Instead of looking for a new career which doesn't require having two good legs, he simply lives in a trailer park near an Air Force base and spends a lot of time in a local bar.
One day, as he's sitting in the bar, something very peculiar happens. From where Karvel is, he can see that it seems as if an invisible force is moving in an expanding spiral across the landscape, knocking things down as it goes along. Some people are injured or killed by this mysterious force, and there's a fair amount of property damage (including portions of the Air Force base). It turns out that this was somehow triggered by the sudden arrival of a black sphere which is eventually determined to be a time machine. (There was a dead human pilot inside the sphere -- I believe his body had been crushed by powerful forces.)
When Karvel first sees the sphere in the spot he calculates was at the center of that expanding spiral, he also finds a two-winged butterfly nearby, which he strongly suspects was on or near the sphere as it made its strange trip. He is shocked by how wrong the butterfly looks. He later shows this to an expert who confirms Karvel's suspicions that the butterfly does not correspond to any winged creature ever recorded as existing in the modern world, but it is possible that millions of years from now some branch of that family might have evolved into such a configuration. This is the main thing that makes Karvel first suspect the sphere is a time machine, instead of a "space ship" or "teleportation device" or whatever.
The sphere later disappears into thin air -- I think someone had gone inside and tried to manipulate the controls. (Which, of course, were not labeled in any language that modern humans could recognize.)
Sometime later, the sphere reappears, with the same sort of invisible wave of force spiraling outward from its "landing site" in France. This time, there was a distinctly nonhuman dead body inside. Eventually, Karvel ends up inside it when it leaves the Twentieth Century again, and it takes him to a time which I think was estimated to be millions of years in the future. (Don't have an exact number; sorry!)
As you remembered, the medical technology in that future era is easily capable of grafting an existing leg onto Karvel's stump to make him able to walk about normally again. This operation is performed. Of course, as you remembered, the new foot is not a mirror image of his other one, since it does not have his DNA, so it needs a different shape and size of shoe. The graft works very well, even though human evolution has taken some strange twists and turns (possibly assisted by deliberate genetic engineering along the way). Earth, in that era, however, is just one of many inhabited planets in the galaxy -- an impoverished backwater that is not considered particularly important -- and there's a man who is the Big Cheese in governing our solar system. He came across to me as being much like a "provincial governor" in the old Roman Empire. He even maintains a personal harem.
When Karvel and the Big Cheese compare notes, they conclude that the strange time-traveling sphere has appeared and disappeared a few times in the 20th Century, and has also appeared, disappeared, reappeared, etc., in this future era (the latest arrival being when it had Karvel aboard). But it was not built by anyone in this future era; they were very surprised by its first arrival and know nothing of its origins. Their best guess is that the controls are currently set for it to jump a certain number of millions of years at a stretch, either forward or backward -- and that the first jump came from that many megayears in Karvel's past.
The plot goes on from there, but I don't feel the need to spoil the ending for you. I believe the above items demonstrate, beyond any reasonable doubt, that we are talking about the same novel. According to an Amazon listing, the text of that book is available as a Kindle download for a mere $2.99 USD if you want to reread it.