ExcelからVBAでSQLiteDBに接続して約500万レコードあるテーブルから５件取得しようとしています。

以下の環境にて ADO を用いた SELECT 時間（データ件数:500万件）を計測してみました。

テーブル定義

実行SQL

SELECT * FROM tb_test;

テスト結果

SQL が簡単な為か、とりあえず、数分かかるということはありませんでした。
CursorLocation = adUseClient としたときの処理が遅いのは、500万件をクライアントカーソルとしてメモリ上にロードしている為と考えられます。
もし、CursorLocation に adUseClient を利用されているのであれば、adUseServer に変更してみてください。

また、TkSQLite が早い理由ですが、ADO に比べて、中間層が少ないのが起因しているのではないかと思います。

＜ADO 経由の DB 接続イメージ＞
         [ADO]
           |
[Microsoft OLE DB Provider for ODBC]
           |
  [SQLite3 ODBC Driver]
           |
       [SQLite3]

参考までに計測に使用したスクリプト（VBScript）を添付します。

' File : SQLiteTest.vbs
' Usage : CScript //Nologo : SQLiteTest.vbs [Enter]
Option Explicit

Const DB_PATH = "C:\SQLite\db_test_5m"

' CursorLocationEnum
Const adUseNone   = 1
Const adUseServer = 2 ' 既定
Const adUseClient = 3

' CursorTypeEnum
Const adOpenForwardOnly = 0 ' 既定
Const adOpenKeyset = 1
Const adOpenDynamic = 2
Const adOpenStatic = 3
Const adOpenUnspecified = -1

' LockTypeEnum
Const adLockReadOnly = 1
Const adLockPessimistic = 2
Const adLockOptimistic = 3
Const adLockBatchOptimistic = 4
Const adLockUnspecified = -1

' DataTypeEnum
Const adInteger = 3
Const adVarChar = 200
Const adFldIsNullable = 32

Dim g_rsTestCase

Call Main()

Sub Main()
    InitTestCase
    Dim rs
    Set rs = g_rsTestCase
    rs.MoveFirst
    While Not rs.BOF And Not rs.EOF
        ConnectTestByTestCaseRecordset rs
        rs.MoveNext
    Wend
End Sub

Sub InitTestCase()
    Set g_rsTestCase = CreateTestCaseRecordset()
    AddTestCase g_rsTestCase, 1, adUseServer, adOpenForwardOnly, adLockReadOnly, "Server,ForwardOnly,ReadOnly"
    AddTestCase g_rsTestCase, 2, adUseServer, adOpenKeyset,      adLockReadOnly, "Server,Keyset     ,ReadOnly"
    AddTestCase g_rsTestCase, 3, adUseServer, adOpenDynamic,     adLockReadOnly, "Server,Dynamic    ,ReadOnly"
    AddTestCase g_rsTestCase, 4, adUseServer, adOpenStatic,      adLockReadOnly, "Server,Static     ,ReadOnly"
    AddTestCase g_rsTestCase, 5, adUseClient, adOpenForwardOnly, adLockReadOnly, "Client,ForwardOnly,ReadOnly"
    AddTestCase g_rsTestCase, 6, adUseClient, adOpenKeyset,      adLockReadOnly, "Client,Keyset     ,ReadOnly"
    AddTestCase g_rsTestCase, 7, adUseClient, adOpenDynamic,     adLockReadOnly, "Client,Dynamic    ,ReadOnly"
    AddTestCase g_rsTestCase, 8, adUseClient, adOpenStatic,      adLockReadOnly, "Client,Static     ,ReadOnly"
End Sub

Function CreateTestCaseRecordset()
    Dim rs
    Set rs = CreateObject("ADODB.Recordset")
    rs.Fields.Append "CaseNo",              adInteger
    rs.Fields.Append "CursorLocationEnum",  adInteger
    rs.Fields.Append "CursorTypeEnum",      adInteger
    rs.Fields.Append "LockTypeEnum",        adInteger
    rs.Fields.Append "CaseName",            adVarChar, 255, adFldIsNullable
    rs.Open
    Set CreateTestCaseRecordset = rs
End Function

Function AddTestCase( ByRef rs, nCaseNo, nCursorLocation, nCursorType, nLockType, strCaseName )
    rs.AddNew
    rs("CaseNo")             = nCaseNo
    rs("CursorLocationEnum") = nCursorLocation
    rs("CursorTypeEnum")     = nCursorType
    rs("LockTypeEnum")       = nLockType
    rs("CaseName")           = strCaseName
    rs.Update
End Function

Sub ConnectTestByTestCaseRecordset( rs )
    Dim nCaseNo
    Dim nCursorLocation
    Dim nCursorType
    Dim nLockType
    Dim strCaseName
    nCaseNo         = rs("CaseNo")
    nCursorLocation = rs("CursorLocationEnum")
    nCursorType     = rs("CursorTypeEnum")
    nLockType       = rs("LockTypeEnum")
    strCaseName     = rs("CaseName")
    
    Call ConnectTestByTestCase( nCaseNo, nCursorLocation, nCursorType, nLockType, strCaseName )
End Sub

Sub ConnectTestByTestCase( nCaseNo, nCursorLocation, nCursorType, nLockType, strCaseName )
    Dim cn
    Set cn = CreateObject("ADODB.Connection")
    cn.ConnectionString = "DRIVER=SQLite3 ODBC Driver;Database=" & DB_PATH
    cn.Open
    cn.CursorLocation = nCursorLocation
    
    Dim strSQL
    strSQL = "SELECT * FROM tb_test;"
    
    Dim dtStart ' 開始時間
    Dim dtEnd   ' 終了時間
    Dim dtDiff  ' 処理時間

    Dim rs
    Set rs = CreateObject("ADODB.Recordset")
    dtStart = Now 
    ' recordset.Open Source, ActiveConnection, CursorType, LockType, option
    rs.Open strSQL, cn, nCursorType, nLockType
    dtEnd = Now
    dtDiff = DateDiff("s", dtStart, dtEnd )
    
    ' 計測結果表示
    WScript.Echo nCaseNo & "," & strCaseName & "," & dtDiff
End Sub

蛇足ですが、ADO のレコードセットの内容を Excel のシートに転記したい場合、「CopyFromRecordset」メソッドが高速なのでお勧めです。

ActiveSheet.Range("A1").CopyFromRecordset rs

＜参考情報＞
■ オートメーションを使用して ADO レコードセットのデータを Excel に転送する方法
http://support.microsoft.com/kb/246335/ja