How to randomly re-insert an element in an array efficiently

Suppose we have an integer array int[] A = {1,2,3,4,5,6,7,8,9}.

Suppose we wanted to pick some random integer from A, and re-insert it somewhere else in the array randomly, like so:

First take some int number = A[random.nextInt(A.length)]

Suppose we randomly select 5, and then re-insert it randomly between 7 and 8, so that A becomes {1,2,3,4,6,7,5,8,9}.

Now, we can obviously do this re-insertion by creating some temporary variable int temp = 5, shifting the subarray {6,7} to the left, and then re-inserting 5 into the index that was occupied by 7 previously. But is there a more efficient way of doing this without shifting some subarray (and without changing to another data structure like linked list)? Because clearly we have some worst case scenario of O(n) where we randomly select A[0] and then have to insert it into A[A.length], requiring all elements in the array to be shifted, which I'd prefer not to have to do.