For me the following solution is working:
1. customizer -> Post information -> Featured Images -> Use Featured Images in Header -> OFF
>>> Shuffle is working again, but post featured image is not shown in post header
2. Install Plugin “Unique Headers” -> edit post and set “custom header” image (same image as featured image).
>>> now shuffle is working and your Post will have ist own header-image