When a crate is part of a public interface, that's harder, indeed. Crates solve it in a few ways:
• crates that expect to be used for interoperability are often split into smaller crates (like API and back-end, or low-level API and high-level API), so that they can evolve some parts without breaking others.
• sometimes breaking changes are technically breaking, but easy to upgrade (e.g. methods renamed, args reordered). In that case most users catch up quickly.
• in desperate cases, a new version can import its own old version and re-export old structs and interfaces that haven't changed, so they're compatible across major versions.
• proper sharing and composition should be done via traits, so that you can implement a trait for any number generator, not just one version of one implementation.
The example of random number generators is a good one, too. There are a lot of applications that require (reproducable!) PRNG sequences and sometimes you have to share PRNGs between modules. Now, looking at the rand crate, I see that the prng part of it was recently mucked around with. If I have two 3rd party modules that I require to share a PRNG that I control (say, noise generators for procedural textures), I cannot compose them if one of them uses the old and one of them uses the new version of the library.