I agree with the other answers that it is obviously related to type and quantity. But I think there is more going on than that. I think the rarity additionally stems from the rarity of the actual fruit it respawns in and the strength and the value the actual Devil fruit gives its user.
There are 11 (canon) Logia fruits, 29 (canon) Zoan fruits and 62 (canon) Paramecia fruits. Going by numbers the Logia fruits are indeed rarer and it is assumed that many more Zoan fruits are out there, compared to Logia fruits. The same logic can indeed be used among the sub-classes of Zoan fruits. There is 1 confirmed Artificial Zoan fruit (with many more to come), 2 Mythical Zoan fruits, 1 Ancient Zoan and 25 other Zoan fruits. Going by numbers the Mythical Zoan and Ancient Zoan fruits are extremely rare. Though, before we can link rarity to numbers, we should wait until Vegapunk explains how they came into existence.
Additionally to type quantity, I do think the type of the actual fruit plays a big role as well. For example, there are many apples in the world. So when Smiley died and the Axolotl model Salamander fruit was reborn in the nearest apple, it showed that that specific fruit will most likely be discovered pretty soon, seeing as apples are so ubiquitous around the world. While if you compare that to the Operation Fruit, which is shaped like a heart, it is safe to assume that when Law dies it will be only able to be reborn in a small part of the world, seeing as there aren't too many fruits shaped like a heart. This would in turn make it difficult to find, making it much rarer than the Axolotl fruit (apple), Giraffe fruit (banana) or String fruit (pear) for example.
Finally, I had found the same question on reddit, at which one of the comments mentioned that the rarity could also be related to the strength of the specific fruit. Stronger Devil fruit powers, inherently make it less likely for the user to die. Considering the fact that many fruits are still unknown in the One Piece universe even today, certain fruits might even be unknown due to their low spawn rate. The less frequently it respawns in different place over the world, the less likely people come in contact, making it seem rarer, then it might be. For example it took Blackbeard many years to find his desired fruit, making it seem a very rare fruit (which it is).
Related to previous paragraph, I believe that the value of a certain fruit adds to its rareness. This does not necessarily mean strength, as we have seen with the Operation fruit. This fruit does not inherently make someone strong. The power is not magic as mentioned by Corazon and requires a lot of knowledge. The World Government priced it at 5 billion Beli, seeing how much power it holds as it is considered the "Ultimate Devil Fruit". Compared to that we have the Revive fruit, which has an extremely low spawn rate, yet nobody seems to care much about this fruit, seeing as it isn't that desired by the majority of people.
On a side note, it is indeed confirmed that only a single instance of any Devil Fruit can be around at the same time. Usopp confirmed this in chapter 447 and Oda double confirmed this in the SBS of Volume 48, Chapter 467.
Reader: Excuse me!! May I pose a serious question to the typically-vulgar SBS?? In Volume 46, Usopp said that the same power doesn't exist twice. But this doesn't make sense with what you said in the Volume 45 SBS... If the Gomu Gomu no Mi was in a book of fruits, then Luffy HAD to have eaten at least the SECOND known example of the fruit! Now, most beautiful and intelligent Ei-chan, explain it all! ✩ P.N. Takafi
Oda: Very sharp of you. But I'm cool. I haven't made any mistakes. As a hint, let me rephrase what Usopp is saying. "The same powers don't exist twice AT THE SAME TIME". How's that? For more detail, you'll just have to wait for a certain professor to make his appearance in the story, and explain exactly what the Devil Fruits REALLY are... Eventually.