Disclaimer
Let me start this answer with a statement that I think must be made: rarity of magic items is a very poor indicator of power level. Of all the indicators of power levels we have in 5e (CR, spell level, character level, gold cost for regular items), rarity of magic items is, by far, the one that least represents the power level of what they represent. For that reason, it is mostly up to the DM to judge how rare an item actually is.
While a Necklace of Fireballs is a Rare item that allows to cast 4 to 9 Fireballs (one of the best 3rd level spells in the game), so is Elixir of Health, which is essentially a one-use Lesser restoration all in one, but still a very situational item that most likely will have the exact same result as the 2nd level spell when used (because you rarely get 5 conditions affecting you at the same time).
Rare seems fine (And I would say solid rare)
Your item is on par with decent consumable rare items. Here is the math:
Let \$p(i)\$ be the conditional (on the fact it did not break in previous hits) probability of the sword breaking at \$i\$-th hit, defined by the sequence $$p(i) = \frac{4 + i}{20}$$
and \$q(i)\$ be the probability of it not breaking $$q(i) = 1 - p(i)$$
Then, the marginal probability of the sword breaking at the \$k\$-th trial is given by
$$P(k) = p(k) \prod_{i=1}^{k-1}q(i) $$
which is basically this vector:
$$[0.2500; 0.2250; 0.1837 ; 0.1365 ; 0.0921 ; 0.0563 ; 0.0310 ; 0.0152 ; 0.0066 ; 0.0025; 0.0008 ; 0.0002]$$
This is an extension to the Geometric Distribution, for those interested.
The expectation is 3.03 attacks. So, the expected damage is \$3.03 \times 21 + 31 = 94.63\$.
On the other hand, you are using your attacks to attack with this weapon, rather than an usual attack. Assume you would attack with a regular Longsword if you were not attacking with this sword, that would give you \$3\times4.5=13.5\$ damage. So, your net gain is 81.13 points of damage.
If you use the Necklace to cast a 9th level Fireball (which is not optimal!), you would do 49 damage on failed save and 24.5 on successful save. Having 3 creatures in the area - which is quite usual, and is the scenario where you would be using the Fireballs, most likely, and one of them failing, already gives you a total damage of 98, or net gain of around 90 (since the modifier is not included in this damage), since you only used one turn.
Overall, I would say the item is slightly worse than the Necklace, but the Necklace is already a top tier Rare item that could easily be "upgraded" to Very Rare.
Some balance comments
The thing with your sword is that is is extremely unreliable. I understand that you wanted to make it unreliable, but I feel you may have gone too far on it. In particular, as I mentioned in the comments, using d20 as the hit dice is very uncommon. I would prefer it being 4d12 - it even deals a little more damage, but more importantly, it reduces the swinginess on the damage roll (see Central Limit Theorem). It is still very swingy in that it may break in the first trial or in the sixth, but, at least, the damage is a little more reliable. If you think this goes against your design philosophy, then keep the d20 as dice roll.
To illustrate the actual distribution of damage, while the average is 94.63, the standard deviation is 42.77, and the distribution looks like this:
You are most likely dealing something around 40 to 80 damage with the sword, and sometimes boom, it lasts to deal more than 200.
Now, consider that consumable magic items are usually used in times of despair. This much unreliability makes the item considerably less powerful. It is clearly way better than an Uncommon item, but it may not be as close to Very Rare as you initially thought.
About critical hits
The reason that I did not want to consider critical hits is that it makes the comparison with other items meaningless. For an enemy that you will be hitting most of the time, the difference is negligible (e.g., AC = 12, Modifier = +8, the difference is 4 points of damage in average, up to 85.2 net damage), while for high AC, while the net total damage will be higher (e.g., AC = 24, net increase = 95.18), the problem is that now you are spending all your turns missing your attacks and dealing actually no damage at all, and then when you hit, you deal lots of damage. Meanwhile, the guy using his Fireballs from the Necklace will be doing a way higher average DPR, because it is actually doing damage every round. Also, if you are facing an enemy that you can only hit on critical hits, you are most likely doing something wrong, because Bounded Accuracy pretty much prevents this scenario.
The only situation where I can see the sword actually approaching Very Rare power levels is if you consider the scenario of an Assassination Rogue using it and you manage to consistently get Surprise, or you can consistently get Unconscious or Paralyzed enemies, forcing automatic critical effects. Then, the massive damage from the dice rolls will be more relevant. But then again, I doubt these are the scenarios the players will be willing to use their magic items on - it's more likely they would like to try it in the Big Boss that is fully awaken and its 8 minion thugs.
