So, I ended up doing this - but it feels a little wrong..

Basicly I just grab the ID of the first record entry in the DynamicRecordList, load it through GetRecord() from RecordStorage, and loop through its fields, adding the Keys and SortOrder to a dictionary. Then, when looping through the records, I look up the key in the dictionary and get the SortOrder. Either way - it's a lot faster than GetAllRecords().

// Get the node
Node node = uQuery.GetNode(nodeID);

// Create list to store records
List<RecordsModel> rmList = new List<RecordsModel>();

// Get form GUID from node
var formGuid = node.GetProperty<string>("formGuid");

// Get all records    
DynamicRecordList records = Library.GetRecordsFromForm(formGuid);

// Define list for field sorting
Dictionary<Guid, int> fieldSorting = new Dictionary<Guid, int>();

// Add fields to sorting if records contain items
if (records.Items.Count() > 0)
{
    // Get the first record
    Record r = recordStorage.GetRecord(new Guid(records.Items.ToList()[0].Id));

    // Loop through the record's fields and add the Key and SortOrder to our sorting list
    foreach (var f in r.RecordFields)
        fieldSorting.Add(f.Key, f.Value.Field.SortOrder);
}

// Loop through the records
foreach (var v in records.Items)
{
    // Create new RecordsModel
    RecordsModel rm = new RecordsModel(v.Id.ToString(), formGuid);

    // Loop through the fields
    foreach (var f in v.RecordFields)
    {
        // Get the SortOrder from the sorting list
        int sortOrder = fieldSorting.ContainsKey(f.Key) ? fieldSorting[f.Key] : 0;

        // Add the field to the RecordsModel
        rm.Fields.Add(f.Value.Field.Caption, new EventRecord()
        {
            Name = f.Value.Field.Caption,
            Value = string.Join(", ", (f.Value.Values.Select(x => x.ToString()).ToArray() ?? new string[0])),
            Index = sortOrder
        });
    }

// Sort the fields by their index
rm.Fields = rm.Fields.OrderBy(x => x.Value.Index).ToDictionary(x => x.Key, x => x.Value);

// Add the RecordsModel to list
rmList.Add(rm);
}

is working on a reply...