Fastest way to pull random records from 3 million records

I have a table with around 3 million barcodes in it that I need to pull a random record from. I read somewhere on here about using something like the below query which it runs in 1.152 seconds but it sometimes pulls the exact same results so thinking I am not doing it right. When I just use ORDER BY RAND() it is taking 8.269 seconds so trying to speed it up. Is there something I am doing incorrect or is there a faster way to pull random records? I am currently using 10.0.38-MariaDB-0+deb8u1

CREATE TABLE `BarcodesAvailable` (
  `barcodeID` INT(11) NOT NULL AUTO_INCREMENT,
  `barcodeNumber` BIGINT(14) NOT NULL,
  `barcodeIDUsing` BIGINT(14) DEFAULT NULL,
  `barcodeStatus` ENUM('Available','In Use','Adding','Unknown') NOT NULL DEFAULT 'Unknown',
  `LastUpdatedAt` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`barcodeID`),
  UNIQUE KEY `UniqueBarcode` (`barcodeNumber`),
  KEY `BarcodeIndex` (`barcodeNumber`),
  KEY `NewBarcodeSearch` (`barcodeNumber`,`barcodeIDUsing`,`barcodeStatus`)
) ENGINE=MYISAM AUTO_INCREMENT=1 DEFAULT CHARSET=latin1



SELECT
  `barcodeID`,
  `barcodeNumber`
FROM
  `BarcodesAvailable`  AS barcode1
JOIN (
  SELECT CEIL(RAND() * ( SELECT MAX(`barcodeID`) FROM `BarcodesAvailable` )) AS `theID` ) AS barcode2 
  ON barcode1.`barcodeID` >= barcode2.`theID` 
  
 WHERE barcode1.barcodeIDUsing IS NULL
 AND barcode1.barcodeStatus = 'Available'
 ORDER BY `barcodeID` ASC
  LIMIT 10