Which version of Kotest are you using
5.9.0

Description
When using the shouldNotBe in a medium-large testset for a property test, it takes unreasonably long. This is very likely a bug, as the performance issue does not occur when using shouldBe or even shouldNotBeIn setOf(<the item>) in the same setup.

How to reproduce
Make an exhaustive containing a large amount of strings (i.e. 50.000x "test"), call .checkAll on it and assert shouldNotBe "notMe" and see the slow performance. Then replace the assertion with shouldNotBeIn setOf("notMe") and observe the performance be fine again. Using shouldBe "test" also works fine.

Stats
When using shouldNotBe, the Test takes 2.5 seconds to run. With shouldNotBeIn, the Test takes ~100ms (25x less!). When profiling just the difference between the statements (and ignoring other test setup and overhead), we get roughly 50ms vs 2200ms in the profiler.
If I add additional shouldNotBe-Statements inside the checkall clause, the tests takes proportionally longer, so the shouldNotBe is a likely culprit and not other test mechanics/overheads.

Conclusion
I am not familiar with the inner workings, but intuitively I would guess the issue might be with the negation of the testcase potentially throwing+catching exceptions internally?